题目一：
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(n)。
分析：遍历数组，只要比num小的，往左排，比num大的，跳过本次操作，这样看来，我们只需要交换满足条件的元素便可以实现题目的要求了。首先我们先建立一个在数组边界外的指针。数组从L至R进行遍历，那么我们的指针当前的位置为index = L-1，在遍历过程中和给定条件进行比较，如满足条件，则交换位置，且index向右移动指针。
代码
public class SortAssignArray {
public static void sort(int[]arr,int num) {
if(arr == null || arr.length<2) {
return;
}
int index = -1; //遍历数组从0开始，那么当前指针的左边界就是-1；
for(int i=0;i<arr.length;i++) {
if(arr[i]<=num) {
swap(arr, ++index, i); //满足条件交换位置，且index向右移动
}else {
continue;
}
}
}
//交换函数
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[]args) {
int []arr = {2,1,8,5,3,9,7,4,10};
int num = 6;
sort(arr, num);
System.out.println(Arrays.toString(arr));
}
}
荷兰国旗问题是面试中经常遇到的算法考题，一起来看题目要求并分析题目求解过程。
问题2：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(n)
这道题和上述的题目有些相似，唯一不同的是加了个等于num放中间这个条件，其实如果你理解了上述的题目的含义，这道题也不难理解了。解这道题需要将数组划分为3部分，即小于num、等于num、大于num，这样一来我们建立三个索引，分别是左边界的，当前位置索引，右边界的索引，通过移动索引并交换位置即可得到答案。
代码
import java.util.Arrays;
//荷兰国旗问题
public class NetherlandsFlag {
public static int[] partition(int[]arr,int L,int R,int num) {
int less = L - 1; //左边界的索引
int more = R + 1; //右边界的索引
int cur = L; //当前位置的索引
while(cur < more) {
if(arr[cur] < num) {
swap(arr, ++less, cur++);
}else if(arr[cur] > num) {
swap(arr, --more, cur);// cur不自加的原因是交换后的arr[cur]可能等于num，也可能小于，或者是大于，需要再做一次判断
}else {
cur++;
}
}
return new int[] {less+1,more-1};
}
public static void swap(int [] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {23,4,2,5,7,42,34,32,7,8,39,45,63,21};
int num = 34;
partition(arr, 0, arr.length-1, num);
System.out.println(Arrays.toString(arr));
}
}
