对撞型，partition类

Kth Largest Element in an Array

• 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;
    }
}

Kth Smallest Element in a Sorted Matrix

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

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 的元素。

/**
 * 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

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

• Princeton 公开课的课件，讲 2-way 和 3-way partitioning

• 一张图说明 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;
    }
}

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】 的两侧，复杂度就越低。

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

顺着 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;
    }
}