首页 > 试题广场 >

数组的partition调整

[编程题]数组的partition调整
  • 热度指数：2052 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个有序数组arr，调整arr使得这个数组的左半部分没有重复元素且升序，而不用保证右部分是否有序
例如，arr = [1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9]，调整之后arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, .....]。
[要求]
时间复杂度为，空间复杂度为


输入描述:
第一行一个整数N。表示数组长度。
接下来一行N个整数，表示数组内元素


输出描述:
输出N个整数为答案数组
示例1

输入

16
1 2 2 2 3 3 4 5 6 6 7 7 8 8 8 9

输出

1 2 3 4 5 6 7 8 9 6 2 7 2 8 8 3
示例2

输入

5
2 3 4 4 5

输出

2 3 4 5 4

备注:

本题有special judge，对于右边的部分，你可以任意输出(在保证合法的前提下)
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n], k=0, p=1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    while(p<n){
        if(a[p]==a[k])
            p++;
        else
            swap(a[p++], a[++k]);
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

发表于 2020-02-27 01:16:50 回复(0)
Java
pein531头像 pein531
并不需要去纠结(n+1)/2，就算左边无重复元素的有序区域超过这个长度也无所谓。给定两个指针orderedBound和ptr，一个指向左边无重复元素有序区域的最后一个元素，另一个指向下一个元素。ptr所指元素只要和orderedBound所指元素相等，为了去重就直接往右走；如果不相等，由于数组本来就是有序的，ptr一定是指到了大于orderedBound所指元素的最小元素，此时让它与有序区域的下一个元素交换，周而复始直到ptr遍历完数组。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = Integer.parseInt(strArr[i]);
        partition(arr);
        for(int i = 0; i < n; i++) System.out.print(arr[i] + " ");
    }
    
    private static void partition(int[] arr) {
        int orderedBound = 0, ptr = 1;
        while(ptr < arr.length){
            // 指针所指的元素跟有序区最后一个元素相等就直接走，不相等就跟有序区的下一个位置交换
            if(arr[orderedBound] != arr[ptr])
                swap(arr, ++orderedBound, ptr);
            ptr++;
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        if(i != j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}
发表于 2021-12-08 17:34:50 回复(0)
C++
木子蓝色头像 木子蓝色
使用快慢双指针 
#include <bits/stdc++.h>

using namespace std;


int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    
    // 数组本身有序，定义快慢指针
    int slow = 0, fast = 0;
    while(fast < n){
        // 碰到与 nums[slow] 不同的元素，把它换到 slow+1 位置
        if(nums[slow] != nums[fast]){
            slow++;
            // 维护 nums[0..slow] ⽆重复
            swap(nums[slow], nums[fast]);
        }
        fast++;    // 相同元素就不断前进
    }
    for(int i = 0; i < n; ++i) cout << nums[i] << " ";
    return 0;
}


发表于 2022-04-12 12:49:15 回复(0)
普罗迷修斯头像 普罗迷修斯 
#include <iostream>
#include <algorithm>
#include <vector>


class Solution {
 public:
    static std::vector<int> getRearrangedList(std::vector<int>& lst) {
        int lst_size = lst.size();
        int max_v = lst[lst_size - 1];
        int j = 0;
        for (int i = 1; i < lst_size; ++i) {
            if (lst[j] == max_v) {
                break;
            }
            if (lst[i] > lst[j]) {
                swap(lst[i], lst[j + 1]);

                ++j;
                if (j + 1 > lst_size - 1) {
                    break;
                }
            }
        }

        return lst;
    }

    static inline void swap(int &a, int &b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
};


// main_b001
int main(int argc, char *argv[]) {
    (void) argc;
    (void) argv;

    int n;
    scanf("%d", &n);

    std::vector<int> in1(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &in1[i]);
    }
    std::vector<int> out1 = Solution::getRearrangedList(in1);
    
    printf("%d", out1[0]);
    for (int i = 1; i < n; ++ i) {
        printf(" %d", out1[i]);
    }
    printf("\n");

    return 0;
}

发表于 2021-10-12 20:56:41 回复(0)
牛客79631828号头像 牛客79631828号 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        partition(arr);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb.toString());
    }
    
    //[0...left]区域都装着升序且不同的数字
    //[left+1...right]装着不确定是否不同的数
    //机制为，让right不停往右走，left记录不同数子数组的最后一个位置
    //但凡碰到一个和arr[left]不同的数，就把它换到left+1位置，同时扩展
    //[0...left]区间，且不用担心排序问题，因为原数组本来就是升序的，而且right
    //也是从左到右遍历的
    public static void partition(int[] arr) {
        if (arr == null || arr.length == 0)
            return;
        int left = 0;
        int right = 1;
        while (right < arr.length) {
            if (arr[right] != arr[left])
                swap(arr, right, ++left);
            right++;
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

发表于 2021-08-22 18:30:52 回复(0)
Python
毓毓子最可爱头像 毓毓子最可爱 
n=input()
number_list=list(input().split())
#结果
res=[]
#利用集合去取重复
s=set()
#保留重复的元素
same=[]

for i in number_list:
    if i in s:
        same.append(i)
    else:
        res.append(i)
        s.add(i)
#在尾部添加重复的元素
for k in same:
    res.append(k)
print(' '.join(res))

发表于 2021-06-17 19:59:27 回复(0)
Python
牛客640734838号头像 牛客640734838号 
def sort_arry(n,l):
    i=0
    j=0
    while j<n and i<n-1:
        if l[j]!=l[i]:
            l[i+1],l[j]=l[j],l[i+1]
            i+=1
        j+=1
    for i in range(n):
        print(l[i],end=" ")

def main():
    n=int(input())
    l=list(map(int,input().split()))
    sort_arry(n,l)
    
if __name__=='__main__':
    main()
        

发表于 2021-05-27 12:24:42 回复(0)
鱼肚白不是鱼头像 鱼肚白不是鱼
这个有序数组一定是递增的吗？
发表于 2021-01-26 22:17:30 回复(0)
头都大了头像 头都大了 
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] nums = Arrays.stream(br.readLine().trim().split(" ")).mapToInt(Integer::parseInt).toArray();
        int slow = 0;
        for(int fast = 1; fast < N; fast++){
            if(nums[slow] != nums[fast]){
                slow++;
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
            }
        }
        System.out.print(nums[0]);
        for(int i = 1; i < N; i++){
            System.out.print(" " + nums[i]);
        }
        System.out.println();
    }
}

发表于 2020-12-09 14:23:43 回复(1)
我要收offer头像 我要收offer
没办法不知道他说的中间点怎么搞得，我把所有的不同数都提前了。省心。 
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(bf.readLine());
        String[] str = bf.readLine().split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(str[i]);
        }
        bf.close();

        int pre = 1, latter = 1;
        
        while (latter < n && pre < n) {
            if (arr[pre] != arr[latter - 1]) {
                int temp = arr[pre];
                arr[pre] = arr[latter];
                arr[latter] = temp;
                latter++;
            }
            pre++;
        }
        StringBuilder sb = new StringBuilder();
        for (int val : arr) {
            sb.append(val + " ");
        }
        System.out.println(sb);
    }
}


发表于 2020-06-07 00:33:05 回复(0)
wayToHappiness头像 wayToHappiness 
import sys

len=int(sys.stdin.readline().split()[0])
arr=sys.stdin.readline().split()

flag=0
go=1
while flag<(len+1)/2:
    if arr[flag]==arr[go]:
        arr.append(arr[go])
        arr.pop(go)
    else:
        go+=1
        flag+=1

print(' '.join(arr))
我觉得自己的想法没有问题，但是就是通不过测试，
怎么可能一个测试用例都通过不了，有大佬能帮忙看看吗？
发表于 2020-05-17 10:49:37 回复(2)
皮蛋秀柚秋头像 皮蛋秀柚秋 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;++i) cin>>v[i];
    int i=0;
    int cur = 1;
    while(cur<n)
    {
        if(v[cur]==v[i])
            ++cur;
        else 
        {
            swap(v[++i],v[cur++]);
        }
    }
    for(int i=0;i<n;++i)
        cout<<v[i]<<" ";

    return 0;
}
发表于 2020-02-11 12:16:01 回复(0)
Java
小星教授头像 小星教授 
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        
        int p = 0;
        for(int i=1;i<n;i++){
            if(arr[i] != arr[p]){
                p++;
                int temp = arr[i];
                arr[i] = arr[p];
                arr[p] = temp;
               
            }
        }
        
        
        
        
        for(int i=0;i<n;i++){
            System.out.print(arr[i]+" ");
        }
	}
}

发表于 2019-10-24 20:23:19 回复(0)
Moon321头像 Moon321
hhh
发表于 2019-10-21 20:56:32 回复(0)
星风雪宇头像 星风雪宇 
#include<iostream>
using namespace std;
int main()
{
    int N;
    while(cin>>N)
    {
        int* arr=new int[N];
        if(N==0)
        {
            break;
        }
        for(int i=0;i<N;i++)    cin>>arr[i];
        if(N==1)
        {
            cout<<arr[0]<<endl;
            break;
        }
        int init_i=0;
        int i=0;
        while(init_i<(N+1)/2)
        {
            if(arr[i]>arr[init_i])
            {
                int temp=arr[i];
                arr[i]=arr[init_i+1];
                arr[init_i+1]=temp;
                init_i++;
                i++;
                if(i>=N) break;
            }
            else
            {
                i++;
                if(i>=N) break;
            }
        }
        for(int i=0;i<N-1;i++) cout<<arr[i]<<' ';
        cout<<arr[N-1]<<endl;
    }
}
有没有大佬帮我看看是哪个case过不去？网上能找到的case都过了
发表于 2019-10-19 00:59:55 回复(0)
提交观点

问题信息

排序
上传者：小小
难度：
15条回答 3005浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号