程序员代码面试指南刷题--第八章.数组的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());
    }
}