首页 > 代码库 > LeetCode OJ 215. Kth Largest Element in an Array

LeetCode OJ 215. Kth Largest Element in an Array

2024-08-22 11:31:01   221人阅读

Find 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.

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

 

Subscribe to see which companies asked this question

解答

用堆排序就好了……不过这个堆是从0开始的，还有点不适应orz

int findKthLargest(int* nums, int numsSize, int k) {
    int i, j, tmp, largest;
    
    for(i = (numsSize - 2) / 2; i >= 0; i--){
        while(i * 2 + 1 < numsSize){
            if(i * 2 + 2 < numsSize&&nums[i * 2 + 1] < nums[i * 2 + 2]){
                largest = i * 2 + 2;
            }
            else{
                largest = i * 2 + 1;
            }
            if(nums[i] < nums[largest]){
                tmp = nums[i];
                nums[i] = nums[largest];
                nums[largest] = tmp;
                i = largest;
            }
            else{
                break;
            }
        }
    }
    for(j = 0; j < k - 1; j++){
        nums[0] = nums[numsSize - 1];
        numsSize--;
        i = 0;
        while(i * 2 + 1 < numsSize){
            if(i * 2 + 2 < numsSize&&nums[i * 2 + 1] < nums[i * 2 + 2]){
                largest = i * 2 + 2;
            }
            else{
                largest = i * 2 + 1;
            }
            if(nums[i] < nums[largest]){
                tmp = nums[i];
                nums[i] = nums[largest];
                nums[largest] = tmp;
                i = largest;
            }
            else{
                break;
            }
        }
    }
    return nums[0];
}

 

LeetCode OJ 215. Kth Largest Element in an Array


联系
我们