yoruru的努力日記

215. Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

SOL：

這一題看似只要把nums排序之後，再回傳第k個就好了，但他會被放在Medium不是沒有理由的。題目要求用O(n)解決，但排序最少也要O(nlogn)，所以不能排序。

解題思路參考：【每日一题】215. Kth Largest Element in an Array, 7/25/2021

原本想用heap的方式解決，但C語言要先實現heap反而有點複雜化，我也參考了 quick select的解法。

loyiCodes #18：更快的排序演算法——快速排序 (Quick Sort)

Leetcode 215. Kth Largest Element in an Array in C [C語言]

但後來覺得Huifeng Guan的binary search反而比較容易寫出來(主要是之前練過binary search)，所以就決定用這個解法了。

原本也是跟著把左右邊界設成INT_MIN、INT_MAX，但運算會發生溢位問題。

所以我就改成題目給的上下限：-10000、10000。(Guan是改成INT_MIN/2、INT_MAX/2)

而且我一開始對於M也是很簡單的寫成(L+R)/2，但因為整數運算的除法會無條件捨去，假設L=0、R=1->M=0會陷入無窮迴圈，所以也跟著寫成M = R - (R-L)/2。

最終程式碼如下：

int count(int* nums, int numsSize, int t){
    int count = 0;
    for(int i = 0; i <numsSize; i++){
        if(nums[i]>=t)
            count++;
    }
    return count;
}
int findKthLargest(int* nums, int numsSize, int k){
    int L = -10000;
    int R = 10000;
    while(L<R){
        int M = R - (R-L)/2;
        if(count(nums,numsSize,M)>=k)
            L=M;
        else
            R=M-1;
    }
    return L;
}

其實這一題我卡了好多天，heap覺得難、quick select也覺得難，原本binary search的解法也覺得複雜，但多想了幾天之後(並且我清明連假也跟著放假了)，好像也沒這麼難了，不過解法跟程式碼還是過於參考Guan的了，要再找時間自己練習幾次。

4/14更新：

對於binary search的邊界條件還是有點模糊，目前找到這個模板，好像能通用(?

二分查找为什么总是写错？

因為 l+r 有可能不小心就溢位了，超出了整數的數值範圍，但 m 是不可能溢位的，因此很多人會用 l+(r-l)/2 這個更安全的寫法。

int count(int* nums, int numsSize, int t){
    int count = 0;
    for(int i = 0; i <numsSize; i++){
        if(nums[i]>=t)
            count++;
    }
    return count;
}
int findKthLargest(int* nums, int numsSize, int k){
    int L = -10001;
    int R = 10001;
    while(L+1<R){
        int M = L+ (R-L)/2;
        if(count(nums,numsSize,M)>=k)
            L=M;
        else
            R=M;
    }
    return L;
}

因為-104 <= nums[i] <= 104，L、R先初始設為不會是答案的 -10001跟10001，使用模板成功^^