自学内容网 自学内容网

大厂面试:找出数组中第k大的数的最佳算法

一.前置条件
假如数组为a,大小为n,要找到数组a中第k大的数。

二.解决方案
1.使用任意一种排序算法(例如快速排序)将数组a进行从大到小的排序,则第n-k个数即为答案。


2.构造一个长度为k的数组,将前k个数复制过来并降序排序。然后依次将 k+1 到 n 位的数分别插入 k 长度的数组中并保持数组长度为k且降序排列。最终长度为k的数组的最后一个元素即是答案。


3.将数组的所有元素构造一个大顶堆,然后删除堆顶元素k次并重新构成大顶堆,则第k次操作后的堆顶元素即为答案。
4.用快速排序的思想不把数组元素全排序的优化算法。
1)先看一下快速排序(降序排序)的算法。

/**
快速排序主函数
a:要排序的数组
left:排序数组左边界索引
right:排序数组右边界索引
*/
public void quickSort(int a[], int left, int right) {
    if (left < right) {
        //算出基准元素索引值index
        int index = partition(a, left, right);
        //对低于index索引的数组递归排序
        quickSort(a, left, index - 1);
        //对高于index索引的数组递归排序
        quickSort(a, index + 1, right);
    }

}

//算出基准元素索引值,此索引值左侧值都大于基准元素值,此索引值右侧值都小于基准元素值
public int partition(int[] num, int left, int right) {
    if (num == null || num.length <= 0 || left < 0 || right >= num.length) {
        return 0;
    }
    //获取数组基准元素的下标
    int prio = num[left + (right - left) / 2]; 
    //从两端交替向中间扫描    
    while (left <= right) {                 
        while (num[left] > prio)
            left++;
        while (num[right] < prio)
            right--;
        if (left <= right) {
            //将不符合条件的元素值交换位置并继续扫描
            swap(num, left, right);        
            left++;
            right--;
        }
    }
    return left;
}

//交换元素
public void swap(int[] num, int left, int right) {
    int temp = num[left];
    num[left] = num[right];
    num[right] = temp;
}

2)我们选择数组区间 a[0…n-1]的中间位置的一个元素 a[n/2]作为 pivot,对数组 a[0…n-1]进行分区,这样数组就分成了三部分,a[0…p-1]、a[p]、a[p+1…n-1]。
如果 p+1=k,那 a[p]就是要求解的答案;如果 k>p+1, 说明第 k 大元素出现在 a[p+1…n-1]区间,我们再按照上面的思路递归的在 a[p+1…n-1]这个区间内查找。同理,如果 k<p+1,那就在 a[0…p-1]区间内递归查找。

3)所以改进后的代码如下:

public int quickSortKthLargest(int a[], int left, int right, int k) {
    if (left < right) {
        //算出基准元素索引值index
        int index = partition(a, left, right);
        //索引对应的值就是第k大的数
        if(index+1==k){
            return a[index];
        }
        //在索引左边继续查找
        else if(index+1>k){
            return quickSortKthLargest(a, left, index-1, k);
        } 
        //在索引右边继续查找
        else{
            return quickSortKthLargest(a, index+1, right, k);
        }
        
    }else{
        return -1;
    }

}


5.在Python中,我们可以使用内置的heapq库来查找数组的第k大元素。heapq库实现了一个堆数据结构,我们可以利用堆的性质来找到数组的第k大元素。
代码如下:

# 返回第k大元素
def get_kth_largest(a, k): 
    # heapq.nlargest(k, a)会返回数组a中最大的k个元素,
    # 然后我们通过[-1]来取得这k个元素中的最后一个,也就是第k大的元素。
    return heapq.nlargest(k, a)[-1]


6.使用最小堆来查找第k大的元素。
首先构建一个空的最小堆。遍历数组a,如果堆的大小小于k,我们就把当前元素加入堆中。如果堆的大小已经达到了k,我们就比较当前元素和堆顶元素(也就是堆中的最小元素),如果当前元素大于堆顶元素,我们就把堆顶元素替换为当前元素,再重新调整最小堆结构。这样,当遍历完整个数组后,堆顶元素就是数组的第k大元素(即是大小为k的最小堆(保存了数组中的最大的k个数)的最小元素)。
代码如下:

def get_kth_largest(a, k):  
    heap = []  
    for num in a:  
        # 若最小堆大小小于k,则将元素插入最小堆
        if len(heap) < k:  
            heapq.heappush(heap, num)  
        else:  
            # 若元素大于最小堆堆顶元素,则插入最小堆并重新排列
            if num > heap[0]:  
                heapq.heapreplace(heap, num)  
    # 堆顶元素即为数组的第k大元素
    return heap[0]  


致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。

若作品对您有帮助,请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。


原文地址:https://blog.csdn.net/cxsjabcabc/article/details/137547626

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!