> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/two_pointers/613-_two_pointersff0c_dui_zhuang_xing_ff0c_partiti.md).

# 对撞型，partition类

### [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)

* **partition 类双指针**

这类问题我一向喜欢用 "<=" 作为循环和跳过元素的判断条件，然后用 swap. 和九章模板上的写法不太一样。

* **需要规范一下自己写 array 问题的变量名用法**
* **left, right 代表移动指针。**
* **start, end 代表区间起始。**

```java
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 的思路写，复杂度一样**

```java
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;
    }
}
```

### [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/)

Quick Select 在 2D 上的应用。

**注意这题复杂度最优的解法是用 heap 做类似多路归并的。不过某种原因目前在 LC 上这种解法要比用 heap 的快一倍。。**

```java
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;
    }
}
```

### [Nuts & Bolts Problem](http://www.lintcode.com/en/problem/nuts-bolts-problem/#)

一道去年曾经卡了我两天的题目。到最后才发现是他们 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 的元素。**

```java
/**
 * 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;
    }
};
```

### [Sort Colors](https://leetcode.com/problems/sort-colors/)

非常有名的算法，人称“荷兰旗算法” [Dutch national flag problem](https://en.wikipedia.org/wiki/Dutch_national_flag_problem)，经典的 "3-way partitioning"算法，用于解决 quick sort 类排序算法中对于重复元素的健壮性问题，在原有 2-way partitioning 的基础上把所有 val == key 的元素集中于数组中间，实现【（小于），（等于），（大于）】的分区。

* [**Princeton 公开课的课件，讲 2-way 和 3-way partitioning** ](http://algs4.cs.princeton.edu/lectures/23DemoPartitioning.pdf)

![](/files/-MUt7_gl2xaKrDzkmYSy)

![](/files/-MUt7_gmxQl66fdb4Um3)

* **一张图说明 Dijkstra 的 3-way partitioning，左右指针维护 < key 和 > key 的元素，\[left , cur - 1] 为 = key 的元素，\[cur, right] 为未知元素。**
* **只有在和 right 换元素时，cur 指针的位置是不动的，因为下一轮还要看一下换过来的元素是不是  < key 要放到左边。**

### O(n) 时间复杂度

```java
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;
    }
}
```

### [Sort Colors II](http://www.lintcode.com/en/problem/sort-colors-ii/)

3-way partition 的进阶版本，k-way partition.

* **利用已知最大和最小 key，维护双指针对撞**
* **数组结构是**
* **【最小key】【cur + unknown】【最大key】**

这种写法的复杂度分析稍微麻烦一些，最大为 O(n \* k/2) 每次复杂度上限为O(n)，最多进行 k / 2 次循环，然而要考虑每次迭代会固定去掉头尾两部分数组，导致 n 逐渐变小，实际的复杂度要根据 k 个数字的分部情况来看，k 的分布越偏向于【1，k】 的两侧，复杂度就越低。

```java
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;
    }

}
```

### [Sort Letters by Case](http://www.lintcode.com/en/problem/sort-letters-by-case/)

顺着 3-way partitioning 的思路，其实这种写法也很适合解决 2-way partitioning 的问题。

```java
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;
    }
}
```