小鑫的算法之路：leetcode0215 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

对于返回第k个最大的元素，可以对整个数组从大到小进行快速排序，然后返回索引为k - 1的元素即可。代码如下：

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        std::sort(nums.begin(), nums.end(), [](int lhs, int rhs) {
            return (lhs > rhs);
        });
        return nums[k - 1];
    }
};

时间复杂度为O(nlogn)，空间复杂度为O(logn)，执行结果如下：

在解法1中，对整个数组进行了排序，而最终仅仅只是为了找到第k个最大的元素，那么很多排序是不必要的。

通过快速排序的切分，可以找到一个随机值在最终排序结果中的索引值，如果该索引值比目标k值小，那么继续在特定区间中查找。该思想与二分查找思想类似，最终时间复杂度可以降低至O(n)。代码如下：

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        return findKthLargest(nums, 0, static_cast(nums.size()) - 1, k - 1);
    }

private:
    int findKthLargest(std::vector& nums, std::ptrdiff_t left, std::ptrdiff_t right, int target_index) 
    {
    	// 当区间只存在一个元素时，其索引值肯定等于target_index，直接返回nums[target_index]
        if (left >= right) {
            return nums[target_index];
        }

        std::ptrdiff_t index = partition(nums, left, right);
        // 如果切分后基准元素的索引与目标索引值一致，直接返回
        if (index == target_index) {
            return nums[index];
        }
		
		// 如果切分后基准元素的索引大于目标索引值，需要继续在左区间查询
        if (index > target_index) {
            return findKthLargest(nums, left, index - 1, target_index);
        }
		
		// 如果切分后基准元素的索引小于目标索引值，需要继续在右区间查询
        return findKthLargest(nums, index + 1, right, target_index);
    }

    std::ptrdiff_t partition(std::vector& data, std::ptrdiff_t left, std::ptrdiff_t right)
    {
        // 随机化处理，随机选择区间内任一一个值作为切分的基准值
        std::ptrdiff_t random = left + rd_() % (right - left + 1);
        std::swap(data[left], data[random]); 

        // 双路切分，循环不变量为data[left + 1, i - 1] >= data[left], data[j + 1, right] <= data[left]
        std::ptrdiff_t i = left + 1;
        std::ptrdiff_t j = right;
        while (true) {
            while ((i <= j) && (data[i] > data[left])) {
                ++i;
            }

            while ((i <= j) && (data[j] < data[left])) {
                --j;
            }

            if (i >= j) {
                break;  // 如果i == j，那么i和j同时指向的值等于基准值，可以直接退出
            }

            std::swap(data[i], data[j]);
            ++i;
            --j;
        }

        std::swap(data[left], data[j]);

        // 因为data[j + 1, right] >= data[left], 那么data[left] >= data[j]，因此可以返回j作为切分索引
        return j;  
    }

private:
    std::random_device rd_;
};

时间复杂度为O(n)，空间复杂度为O(logn)，执行结果如下：