程式員代碼面試指南刷題--第八章.數組的partition調整

題目描述

給定一個有序數組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, …]。

[要求]

時間複雜度為O(n)O(n)O(n)，空間複雜度為O(1)O(1)O(1)

輸入描述:

第一行一個整數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
           

解法一：類似荷蘭國旗

import java.io.*;
public class Main{
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static int[] fun(int[] arr){
        if(arr==null||arr.length<3) return arr;
        int i = 0;
        int l = 1;
        while(l<arr.length){
            if(arr[i]!=arr[l]){
                i++;
                int tmp = arr[i];
                arr[i] = arr[l];
                arr[l] = tmp;
            }
            l++;
        }
        return arr;
    }
    public static void main(String[] args)throws IOException{
        int len = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().trim().split(" ");
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = Integer.parseInt(ss[i]);
        }
        arr = fun(arr);
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<arr.length;i++){
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
}