Quick Sort/Select

Quick select/Partition

Partition Array

• 给定array和一个数K,

• 要求把<K的数都放到K的左边，>=K 的数都放到K的右边

• 返回partition后从左到右第一个K所在的index

• 这题是partition的基本功

• 建立两个runner pointer, left and right, while loop

• left用来找下一个>=k的数，right找下一个<K的数，然后交换, 直到left > right

• 这样array就被partition成了两部分，左边部分都是<K的数，right是最后一个。右边部分都是>=K的数，left就是右边部分的起始位置

• 注:标准的partition 是把array分成3部分，左边部分< K, 右边部分> K, 中间可能有n个 重复的K。这样判断条件就只是nums[begin] < k和nums[end] > k,不加"<="或者">="

    public int partitionArray(int[] nums, int k) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int begin = 0, end = nums.length - 1;
        while (begin <= end) {
            while (begin <= end && nums[begin] < k) {
                begin++;
            }
            while (begin <= end && nums[end] >= k) {
                end--;
            }
            if (begin<= end) {
                swap(nums, begin, end);
                begin++;
                end--;
            }
        }
        return begin;
    }
    private void swap(int[] nums, int begin, int end) {
        int tmp = nums[begin];
        nums[begin] = tmp;
        nums[end] = nums[begin];
    }

Kth largest element in an array

• 这题如果面试遇到，想到最优解Quick select之前应该先讨论sort and heap的两种解法

• 把array partition成3部分，左边部分< K, 右边部分> K, 中间可能有n个 重复的K。这样判断条件就只是nums[begin] < k和nums[end] > k,不加"<="或者">="

Partition Array

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    //quickSelect, return value
    private int quickSelect(int[] nums, int begin, int end, int k) {
        if (begin >= end) {
            return nums[k];
        }
        int left = begin, right = end;
        int pivot = nums[(begin + end) / 2];
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            } 
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        if (k <= right) {
            return quickSelect(nums, begin, right, k);
        }
        if (k >= left) {
            return quickSelect(nums, left, end, k);
        }
        return nums[k];
    }

    private void swap(int[] nums, int begin, int end) {
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
    }
}