笔试面试算法经典--数组partition调整使数组的左部分单调有序

【题目】 给定一个有序数组arr，调整使得数组的左部分无重复元素且有序，右边部分不要求。如数组arr[]={1,2,2,2,3,3,4,5,6,9,9} ;调整过后可以为：[1, 2, 3, 4, 5, 6, 9, 2, 3, 2, 9] 。

---

思路：使用标记 u 其中arr[0…u] 表示已经处理过的没有重复元素且有序的区间，从arr[u+1…i-1]表示有重复元素的部分。则算法主要分为下面两部分。 1. 比较 arr[i] 与 arr[u] 是否相同如果不同，则将 arr[i] 的值赋给arr[u+1],u++; 2. i++遍历数组。 例如的数组：arr[]={ 1, 2, 2, 2, 3, 3, 4, 5} 的处理过程。

下图中：绿色–没有重复且有序部分 黄色–指针遍历到的位置 棕色–重复区域

⑤重复操作直到遍历到数组的最后一个元素。

1.刚开始是u=0指向1, i=1指向2， 因为arr[u]!=arr[i], 此时，arr[u+1]=arr[i],i++,u=1,i=2,

2.此时i=2指向2，u=1指向2，arr[u]=arr[i]所以不处理，只进行 i++。

3.循环上面操作直至数组遍历完成。

---

import java.util.Arrays; public class NORepeatInLeft { public static void main(String[] args) { int arr[]={1,2,2,2,3,3,4,5,6,9,9}; norepeat(arr); System.out.println(Arrays.toString(arr)); } public static void norepeat(int arr[]) { if(arr==null||arr.length==0) return; int u=0; //u刚开始时赋值0，i赋值1。 for(int i=1;i<arr.length;i++) { if(arr[i]!=arr[u]) { swap(arr,i,u+1); u++; //如果arr[i]!=arr[u]交换他们的值，然后u++， } } } //交换两个值的函数 public static void swap(int arr[],int i,int j) { int temp; temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } }