欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Kth Largest Element in an Array Leetcode #215 题解[C++]

程序员文章站 2022-04-25 13:32:56
...

题目来源


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

题目理解


ind the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

找出给定数组中第 k 大的元素. 假定 k 总是合法的.

解题思路


这道题相信能够直接看出最简单粗暴的解法, 即使用快速排序先将数组排好序, 再直接找出第 k 大的元素.

但回想一下快速排序的过程, 我们完全可以在这个基础上进行优化. 注意到, 每趟快排都会有一个分区的过程, 在这个过程里, 我们可以直接判断第 k 大的数会落在哪一边, 进而只对一边进行再查找, 就能够节省将近一半的工作量. ( 平均情形 )

代码实现


这段代码在时间排序上表现比较一般, 这一方面是因为这道题中许多人直接用了标准库中的make_heap, sort, dequeue等手段, 算是走了捷径; 另一个原因是我用的快排版本是方便记忆的和理解的, 并不是较快版本的快排.

#include <iostream>
#include <vector>
using namespace std;

#include <iostream>

using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return recursiveFind(0, nums.size() - 1, nums.size()-k,nums);
    }
    int recursiveFind(int left, int right, int k, vector<int>&nums) {
        int lo = left;
        int hi = right;
        int key = nums[lo];
        while (lo < hi) {
            while (lo < hi&&nums[hi] >= key) --hi;
            nums[lo] = nums[hi];
            while (lo < hi&&nums[lo] <= key) ++lo;
            nums[hi] = nums[lo];
        }
        nums[lo] = key;
        if (k == lo) return nums[lo];
        else if (k  > lo) return recursiveFind(lo + 1, right, k, nums);
        else return recursiveFind(left, lo - 1, k, nums);
    }
};

Kth Largest Element in an Array Leetcode #215 题解[C++]

相关标签: Algorithm