给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。
要求额外空间复杂度O(1),时间复杂度O(N)
思想: 我们可以定义三个指针,一个less代表已经排好小值的最大索引,一个more代表已经拍好的大值的最小索引,curr表示当前索引,利用curr不断驱动数据分区,当curr指针碰到more时候停止 代码
public class NetherlandsFlag {
public static void main(String[] args){
/*int[] test=generateRandomArray(10,100);
int[] copy=copyArray(test);*/
int [] numarr={99,22,44,88,33,11,55,66};//
partition(numarr,55);
printArray(numarr);
}
public static void partition(int[] arr,int num ){
int less=-1;
int more=arr.length;
int curr=0;
while (curr<more){
if (arr[curr]>num){
more--;
swap(arr,more,curr);
}
else if (arr[curr]==num){
curr++;
}
else if (arr[curr]<num){
less++;
swap(arr,less,curr);
curr++;
}
}
}
}