给定一个有序数组arr, 调整arr使得这个数组的左半部分没有重复元素且升序,而且不用保证右边是否有序
分区就ok了 u区是 无重复且升序的 u是这个区域的最后位置,初始u=0
i做从左到右的遍历,在arr[u+1....i]上是不保证没有重复元素且升序的区 i是这个区域的最后位置
i向右移动 因为数组整体有序,如果arr[i] !=arr[u] 说明当前arr[i]应该加入到 u区域里 则交换之! 如果arr[i]==arr[u] 说明当前数arr[i]的值之前已经加入到u区域里
上代码:
package TT;
public class Test81 {
public void leftUnique(int[] arr){
if(arr==null || arr.length<2){
return;
}
int u = 0;
int i =1;
while(i != arr.length){
if(arr[i++]!=arr[u]){
swap(arr, ++u, i-1);
}
}
}
}