查找数组中第k大的数算法代码

admin 2020-03-21 PM 4℃ 0条

问题:
查找出一给定数组中第k大的数。例如[3,2,7,1,8,9,6,5,4],第1大的数是9,第2大的数是8……

思路:
1. 直接从大到小排序,排好序后,第k大的数就是arr[k-1]。
2. 只需找到第k大的数,不必把所有的数排好序。我们借助快速排序中 partition过程,一般情况下,在把所有数都排好序前,就可以找到第k大的数。我们依据的逻辑是,经过一次partition后,数组被pivot 分成左右两部分:S左、S右。当S左的元素个数|S左|等于k-1时,pivot即是所找的数;当|S左|小于k-1,所找的数位于S右中;当|S 左|>k-1,所找的数位于S左中。显然,后两种情况都会使搜索空间缩小。

代码:

int Partition(int *arr, int from, int to)
{
    int i, j;
    i = j = from;
    while (j <= to)
    {
        if (arr[j] >= arr[to]) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
        j++;
    }
    return i - 1;
}
int quickSelect(int *s, int k, int left, int right)
{
    if (left == right) return s[left];
    int i;
    i = Partition(s, left, right);
    if (i - left + 1 == k) {
        return s[i];
    }
    else if (i - left + 1 < k) {
        return quickSelect(s, k - (i - left + 1), i + 1, right);
    }
    else return quickSelect(s, k, left, i - 1);
}
int findKthLargest(int* nums, int numsSize, int k) {
    return quickSelect(nums, k, 0, numsSize - 1);
}

至于”查找数组中第k小的数“,那自然可以举一反三,同样处理了。

标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~