对撞型,partition类
partition 类双指针
这类问题我一向喜欢用 "<=" 作为循环和跳过元素的判断条件,然后用 swap. 和九章模板上的写法不太一样。
需要规范一下自己写 array 问题的变量名用法
left, right 代表移动指针。
start, end 代表区间起始。
public class Solution {
public int findKthLargest(int[] nums, int k) {
return partition(nums, k, 0, nums.length - 1);
}
private int partition(int[] nums, int k, int start, int end){
int pivot = nums[start];
int left = start;
int right = end;
while(left <= right){
while(left <= right && nums[left] >= pivot) left++;
while(left <= right && nums[right] <= pivot) right--;
if(left < right) swap(nums, left, right);
}
swap(nums, start, right);
if(k == right + 1) return nums[right];
if(k > right + 1){
return partition(nums, k, right + 1, end);
} else {
return partition(nums, k, start, right - 1);
}
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
这题也可以用 3-way partitioning 的思路写,复杂度一样
public class Solution {
public int findKthLargest(int[] nums, int k) {
return partition(nums, k, 0, nums.length - 1);
}
private int partition(int[] nums, int k, int start, int end){
int pivot = nums[start];
int left = start;
int right = end;
int cur = start;
while(cur <= right){
if(nums[cur] > pivot){
swap(nums, cur ++, left ++);
} else if (nums[cur] < pivot){
swap(nums, cur, right--);
} else {
cur ++;
}
}
right = cur - 1;
if(k == right + 1) return nums[right];
if(k > right + 1){
return partition(nums, k, right + 1, end);
} else {
return partition(nums, k, start, right - 1);
}
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
Quick Select 在 2D 上的应用。
注意这题复杂度最优的解法是用 heap 做类似多路归并的。不过某种原因目前在 LC 上这种解法要比用 heap 的快一倍。。
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
if(matrix == null || matrix.length == 0) return -1;
int rows = matrix.length;
int cols = matrix[0].length;
return kthHelper(matrix, 0, rows * cols - 1, k);
}
private int kthHelper(int[][] matrix, int start, int end, int k){
int rows = matrix.length;
int left = start;
int right = end;
int pivot = matrix[start / rows][start % rows];
while(left <= right){
while(left <= right && matrix[left / rows][left % rows] <= pivot) left++;
while(left <= right && matrix[right / rows][right % rows] >= pivot) right--;
if(left < right) swap(matrix, left, right);
}
swap(matrix, start, right);
if(right + 1 == k){
return matrix[right / rows][right % rows];
} else if(right + 1 < k){
return kthHelper(matrix, right + 1, end, k);
} else {
return kthHelper(matrix, start, right - 1, k);
}
}
private void swap(int[][] matrix, int a, int b){
int rows = matrix.length;
int temp = matrix[a / rows][a % rows];
matrix[a / rows][a % rows] = matrix[b / rows][b % rows];
matrix[b / rows][b % rows] = temp;
}
}
一道去年曾经卡了我两天的题目。到最后才发现是他们 test case 写错了。。。
这题和 quick select 的 partition 思路完全一致,但是细节不同。
所有的不等式判断条件都没有 '=' 号。
所有元素 1-1 对应,不会有多个元素等于 pivot.
pivot 元素来自外部,而不是内部已知位置。
如果 partition array 不带等于号的写,数组里有多个元素等于 pivot 就会挂了。
原因在于,在这题中,每次 partition 用的是外部元素,而且 array 里有且只有一个正确 pivot 元素与其对应,所以最终一定会 left == right 停留在 pivot 上。
这题如果像 partition 一样全带 '=' 去判断,其实也是可以正确把数组 partition 的,但是不同于 quick select 里面固定用 num[start] 做 pivot,这种写法里面我们不知道正确的 pivot 位置在哪。
假如按 left <= right,各种 cmp >= 0 <= 0 挪动
【2,1,|7|,8,3,9,|4|,5,6】,pivot = 5
【2,1,4,|8|,|3|,9,7,5,6】
【2,1,4,|3|,|8|,9,7,5,6】
总的来说;
全带等号的比较方式,可以 partition,要手动找 pivot 位置做收尾 swap,适用于自己选好 pivot 的情况
全不带等号的比较方式,如果 pivot 元素有唯一对应,可以 partition 并且 left == right 停留在 pivot 上;否则多个等于 pivot 时会死循环,因为不带等号无法让指针跨过 等于 pivot 的元素。
/**
* public class NBCompare {
* public int cmp(String a, String b);
* }
* You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
* if "a" is bigger than "b", it will return 1, else if they are equal,
* it will return 0, else if "a" is smaller than "b", it will return -1.
* When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
public class Solution {
/**
* @param nuts: an array of integers
* @param bolts: an array of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
public void sortNutsAndBolts(String[] nuts, String[] bolts, NBComparator compare) {
// write your code here
helper(nuts, bolts, compare, 0, nuts.length - 1);
}
private void helper(String[] nuts, String[] bolts, NBComparator compare,
int start, int end){
if(start >= end) return;
int pivot = partitionNuts(nuts, bolts[start], start, end, compare);
partitionBolts(bolts, nuts[pivot], start, end, compare);
helper(nuts, bolts, compare, start, pivot - 1);
helper(nuts, bolts, compare, pivot + 1, end);
}
private int partitionNuts(String[] nuts, String bolt, int start, int end,
NBComparator compare){
int left = start;
int right = end;
while(left < right){
while(left < right && compare.cmp(nuts[left], bolt) < 0) left ++;
while(left < right && compare.cmp(nuts[right], bolt) > 0) right --;
if(left < right) swap(nuts, left, right);
}
// 最终 left = right ,都停留在 pivot 上
return left;
}
private int partitionBolts(String[] bolts, String nut, int start, int end,
NBComparator compare){
int left = start;
int right = end;
while(left < right){
while(left < right && compare.cmp(nut, bolts[left]) > 0) left ++;
while(left < right && compare.cmp(nut, bolts[right]) < 0) right --;
if(left < right) swap(bolts, left, right);
}
return right;
}
private void swap(String[] arr, int a, int b){
String temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
};
非常有名的算法,人称“荷兰旗算法” Dutch national flag problem,经典的 "3-way partitioning"算法,用于解决 quick sort 类排序算法中对于重复元素的健壮性问题,在原有 2-way partitioning 的基础上把所有 val == key 的元素集中于数组中间,实现【(小于),(等于),(大于)】的分区。

一张图说明 Dijkstra 的 3-way partitioning,左右指针维护 < key 和 > key 的元素,[left , cur - 1] 为 = key 的元素,[cur, right] 为未知元素。
只有在和 right 换元素时,cur 指针的位置是不动的,因为下一轮还要看一下换过来的元素是不是 < key 要放到左边。
O(n) 时间复杂度
public class Solution {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
int i = 0;
while(i <= right){
if(nums[i] < 1){
swap(nums, left++, i++);
} else if(nums[i] > 1){
swap(nums, i, right--);
} else {
i ++;
}
}
}
private void swap(int[] nums, int a, int b){
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
3-way partition 的进阶版本,k-way partition.
利用已知最大和最小 key,维护双指针对撞
数组结构是
【最小key】【cur + unknown】【最大key】
这种写法的复杂度分析稍微麻烦一些,最大为 O(n * k/2) 每次复杂度上限为O(n),最多进行 k / 2 次循环,然而要考虑每次迭代会固定去掉头尾两部分数组,导致 n 逐渐变小,实际的复杂度要根据 k 个数字的分部情况来看,k 的分布越偏向于【1,k】 的两侧,复杂度就越低。
class Solution {
/**
* @param colors: A list of integer
* @param k: An integer
* @return: nothing
*/
public void sortColors2(int[] colors, int k) {
// write your code here
int left = 0;
int right = colors.length - 1;
int cur;
int lowColor = 1;
int highColor = k;
while(lowColor < highColor){
cur = left;
while(cur <= right){
if(colors[cur] == lowColor){
swap(colors, cur ++, left ++);
} else if(colors[cur] == highColor){
swap(colors, cur, right --);
} else {
cur ++;
}
}
lowColor ++;
highColor --;
}
}
private void swap(int[] colors, int a, int b){
int temp = colors[a];
colors[a] = colors[b];
colors[b] = temp;
}
}
顺着 3-way partitioning 的思路,其实这种写法也很适合解决 2-way partitioning 的问题。
public class Solution {
/**
*@param chars: The letter array you should sort by Case
*@return: void
*/
public void sortLetters(char[] chars) {
//write your code here
int left = 0;
int right = chars.length - 1;
int cur = 0;
while(cur <= right){
if(chars[cur] >= 'a'){
swap(chars, cur ++, left ++);
} else if(chars[cur] < 'a'){
swap(chars, cur, right--);
} else {
cur ++;
}
}
}
private void swap(char[] chars, int a, int b){
char temp = chars[a];
chars[a] = chars[b];
chars[b] = temp;
return;
}
}
Last updated
Was this helpful?