[LeetCode] 算法 - Quick Select & Q

Quick Select

平均时间复杂度：O(n)
最坏时间复杂度：O(n^2) - 取决于pivot情况

public class Solution {
  private void quickSelect(int[] nums, int l, int r, int k) {
        if (l >= r) return;
        int mid = partition(nums, l, r);
        if (mid - l + 1 == k) {
            return nums[mid];
        } else if (mid - l + 1 < k) {
            quickSelect(nums, mid + 1, r, k - (mid - l + 1));
        } else { // mid - l + 1 > k
            quickSelect(nums, l, mid - 1, k);
        }
    }
    private int partition(int[] nums, int l, int r) {
        int base = l;
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) { // 注意点：先动右边的
                r--;
            }
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            swap(nums, l, r);
        }
        // l成为区分左右两边的点
        swap(nums, base, l); 
        return l;
    }
    
    private void swap(int[] n, int i, int j) {
        int tmp = n[i];
        n[i] = n[j];
        n[j] = tmp;
    }
}

Quick Sort

平均时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2) - 取决于pivot情况

public class Solution {
  private void quickSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int mid = partition(nums, l, r);
        quickSort(nums, l, mid - 1);
        quickSort(nums, mid + 1, r);
    }
    private int partition(int[] nums, int l, int r) {
        int base = l;
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) {
                r--;
            }
            while (l < r && nums[l] <= pivot) {
                l++;
            }
            swap(nums, l, r);
        }
        // l成为区分左右两边的点
        swap(nums, base, l); 
        return l;
    }
    
    private void swap(int[] n, int i, int j) {
        int tmp = n[i];
        n[i] = n[j];
        n[j] = tmp;
    }
}

比较

总体而言，Quick Select采用和Quick Sort类似的步骤。首先选定一个pivot，然后根据每个数字与该pivot的大小关系将整个数组分为两部分。那么与Quick sort不同的是，Quick Select只考虑所寻找的目标所在的那一部分子数组，而非像Quick Sort一样分别再对两边进行分割。正是因为如此，Quick Select将平均时间复杂度从O(nlogn)降到了O(n)。

Reference
https://www.jianshu.com/p/52f90fe2b141