算法总结之 数组的partition调整

时间:2021-12-19 19:52:33

 给定一个有序数组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);
}
}

}


}