菜鸟笔记
提升您的技术认知

无序数组中找第k大的数

阅读 : 263

类快排算法

leetcode215

由于只要求找出第k大的数,没必要将数组中所有值都排序。

快排中的partition算法,返回key在数组中的位置的cnt(相对于left的偏移量),如果cnt正好等于k,那么问题则得到解决;如果cnt小于k,去左边找第k个;如果cnt>k,则去右边找第k-cnt个。直到key的位置等于k-1,则找对问题的解。

/*快排中的划分算法*/
int partition(int* input, int low, int high)
 {
    int tmp = input[low]; // 取一个基准元素

    while (low < high) {
        while (low < high && input[high] >= tmp) {
            high--;
        }
        input[low] = input[high];

        while (low < high && input[low] <= tmp) {
            low++;
        }
        input[high] = input[low];
    }

    input[low] = tmp;
    return low;
}

// 这里得到的是第k小,自己n-k转换下即可, 或者改下划分函数
int findK(int* array, int left, int right, int k) {
    //printf("%d %d %d\n", left, right, k);
    int i = partition(array, left, right);
    int cnt = i - left + 1;
    if (k == cnt) {
        return array[i];
    } else if (k < cnt) {
        return findK(array, left, i - 1, k);
    } else if (k > cnt) {
        return findK(array, i + 1, right, k-cnt);
    }
    return 0;
}

此解法的时间复杂度为O(N*lgK),logK次每次O(N),优于排序解法

最小堆解法

构造一个大小为k的最小堆,堆中根节点为最小值。如果数组中最大的几个数均在堆中,那么堆中根节点的值就是问题的解。

可以用STL中的优先队列实现,因为优先队列的内部就是最大堆/最小堆实现的。

此解法的时间复杂度O(NlogK),N次logK。但是相比与类快速排序算法,需要额外的存储空间。