本文共 1043 字，大约阅读时间需要 3 分钟。

问题一   

给定一个数组arr，和一个数num，请把小于等于num的数放在数 组的左边，大于num的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)

思路：遍历的过程指针指向的位置如果小于等于num，则小于等于区域的下一个数和  遍历过程的指针指向的数进行交换

问题二

（荷兰国旗问题） 给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的 右边。

要求额外空间复杂度O(1)，时间复杂度O(N)

要求额外空间复杂度O(1)即不用额外的辅助数据结构，只用有限几个变量

时间复杂度O(N)即遍历数组的次数是固定的

less指针指向小于等于num区域，more指针指向大于等于num区域。current指针进行遍历。

1）current指针遍历过程指向的数如果小于num，小于等于区域的下一个数和current指向的数进行交换，current++，less++

2）current指针遍历过程指向的数如果大于num，more指针（大于等于区域）的下一个数和current指向的数进行交换，再次判断current指向的数的值是否大于num，如果大于，继续和more指针（大于等于区域）的下一个数进行交换。

3）如果current指针指向的数和num相等，则current++。

具体代码如下：

public static int[] partition(int[] arr, int l, int r, int num) {   int less = l - 1;   int more = r + 1;   while (l < more) {      if (arr[l] < num) {         swap(arr, ++less, l++);      } else if (arr[l] > num) {         swap(arr, --more, l);      } else {         l++;      }   }   //等于区域的边界   return new int[] { less + 1, more - 1 };}// for testpublic static void swap(int[] arr, int i, int j) {   int tmp = arr[i];   arr[i] = arr[j];   arr[j] = tmp;}

转载地址：http://inuwi.baihongyu.com/