leetCode-0215_数组中的第K个最大元素

Posted on | In |

题目描述

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.

Example 1:

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

Example 2:

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

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

中文题目

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

示例 1:

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

示例 2:

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

说明:

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

解决方法

方法一
  • 描述

核心思想是每次都要先找一个中枢点Pivot，然后遍历其他所有的数字，像这道题从小往大排的话，就把小于中枢点的数字放到左半边，把大于中枢点的放在右半边，这样中枢点是整个数组中第几大的数字就确定了，虽然左右两部分不一定是完全有序的，但是并不影响本题要求的结果，所以我们求出中枢点的位置，如果正好是k-1，那么直接返回该位置上的数字；如果大于k-1，说明要求的数字在左半部分，更新右边界，再求新的中枢点位置；反之则更新右半部分，求中枢点的位置；

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdbool.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int a[], int left, int right)
{
    int i = left;
    int j = left;
    for (j = left; j < right; j++) {
        if (a[j] > a[right]) {
            if (i != j) {
                swap(a + i, a + j);
            }
            i++;
        }
    }
    
    swap(a + i, a + right);
    return i;
}

int findKthLargest(int* nums, int numsSize, int k) {
    int left = 0;
    int right = numsSize - 1;
    while (true) {
        int pos = partition(nums, left, right);
        if (pos == k - 1) {
            return nums[pos];
        }
        else if (pos > k - 1) {
            right = pos - 1;
        }
        else {
            left = pos + 1;
        }
    }
}

/**
 测试
 */
void test()
{
    int arr1[6] = { 3, 2, 1, 5, 6, 4};
    int k1 = 2;
    int max1 = findKthLargest(arr1, 6, k1);
    printf("第%d大元素是%d\n",k1,max1);
    
    int arr[9] = { 3,2,3,1,2,4,5,5,6 };
    int k = 4;
    
    int max = findKthLargest(arr, 9, k);
    printf("第%d大元素是%d\n",k,max);
}

题目来源

Kth Largest Element in an Array

数组中的第K个最大元素