# 对撞型，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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/two_pointers/613-_two_pointersff0c_dui_zhuang_xing_ff0c_partiti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.