LeetCode_Day26

[215] 数组中的第K个最大元素

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/description/

• algorithms
• Medium (64.59%)
• Likes: 992
• Dislikes: -
• Total Accepted: 298.5K
• Total Submissions: 462.1K
• Testcase Example: ‘[3,2,1,5,6,4]\n2’

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

方法1: 快速查找算法

第K问题, 可以使用快速查找算法

1. 我的算法

class Solution {
public:
    int quick_select(vector<int> & nums, int left, int right){
        int pivotkey = rand() % (right - left) + left; //随机选择
        swap(nums[pivotkey], nums[left]);
        int pivot = nums[left];
        while(left < right){
            while(left < right && nums[right] <= pivot) --right;
            nums[left] = nums[right];
            while(left < right && nums[left] >= pivot) ++left;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
        int findKthLargest(vector<int>& nums, int k) {
            int left = 0, right = nums.size() - 1, mid = 0, target = k - 1; // target 指第k大的数的索引
            while(left < right){
                mid = quick_select(nums, left, right);
                if(mid == target){
                    return nums[mid];
                } else if (mid < target){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return nums[left];
        }
};

经测试, 随机选取 pivotkey 会极大的提高效率

• 随机选择前:

  

• 随机选择后:

  

复杂度分析:

• 时间复杂度: O(n) , 由于随机选择 pivotkey , 故不会出现 $O(n^2)$ 的最坏情况
• 空间复杂度: O(1)