首页

空间复杂度为O(1)的模板。

快速选择模板

215. 数组中的第K个最大元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quickSelect(nums, 0, len(nums) - 1, len(nums) - k + 1)

    def quickSelect(self, nums, left, right, k):
        """
        在nums[left:right+1]中查找第k小的元素
        """
        if left == right:
            return nums[left]

        pivot_index = self.partition(nums, left, right)

        if pivot_index - left + 1 == k:
            return nums[pivot_index]
        elif pivot_index - left + 1 < k:
            return self.quickSelect(nums, pivot_index + 1, right, k - (pivot_index - left + 1))
        else:
            return self.quickSelect(nums, left, pivot_index - 1, k)

    def partition(self, nums, left, right):
        """
        对nums[left:right+1]进行分割，使得nums[left]左边的元素都小于等于nums[left]，nums[left]右边的元素都大于等于nums[left]
        """
        # 此处要随机选择一个元素，不然面对
        idx = random.randint(left, right);
        nums[left], nums[idx] = nums[idx], nums[left]
        pivot = nums[left]
        low, high = left, right
        while low < high:
            # 此处不能写nums[high] >= pivot，因为如果写了等号，那么当数组中存在重复元素时，每次分割问题规模不会减半，而是正好减1
            while low < high and nums[high] > pivot:
                high -= 1
            if low < high:
                nums[low] = nums[high]
                low += 1
            # 此处同理
            while low < high and nums[low] < pivot:
                low += 1
            if low < high:
                nums[high] = nums[low]
                high -= 1
        nums[low] = pivot
        return low

快排模板

912. 排序数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] sortArray(int[] nums) {
        quicksort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quicksort(int[] nums, int l, int r){
        if(l >= r){
            return;
        }
        // 随机选择一个元素，尽量保证每次尽量分得平均
        int idx = new Random().nextInt(r - l + 1) + l;
        int pivot = nums[idx];
        nums[idx] = nums[l];
        nums[l] = pivot;
        int low = l, high = r;
        while(low < high){
            // 此处不能写nums[high] >= pivot，因为如果写了等号，那么当数组中都是重复元素时，
            // 每次分割问题规模不会减半，而是正好减1
            while(low < high&&nums[high] > pivot){
                high--;
            }
            if(low < high){
                nums[low++] = nums[high];
            }
            // 此处同理
            while(low < high&&nums[low] < pivot){
                low++;
            }
            if(low < high){
                nums[high--] = nums[low];
            }
        }
        nums[low] = pivot;
        quicksort(nums, l, low - 1);
        quicksort(nums, low + 1, r);
    }
}