java算法之寻找最小的k个数--1
1.快排,不讲了 2.定义一个小根堆,比如priorityqueue,添加数据,利用小根堆每次弹出最小值即可
这个题目的两种解法都比较简单,时间复杂度也还好,就不讲这题了
这里引入一个类似题目的变种
谷歌面试题：输入是两个整数数组，他们任意两个数的和又可以组成一个数组，求这个和中前k个数怎么做？
分析：
“假设两个整数数组为A和B，各有N个元素，任意两个数的和组成的数组C有N^2个元素。
那么可以把这些和看成N个有序数列：
A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…
A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…
…
A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=…
问题转变成，在这N^2个有序数列里，找到前k小的元素”具体代码可以见大佬得. https://blog.csdn.net/edwards_june/article/details/54407709
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/12/31 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录