java（87）
一道面试题
有20个数组，每个数组有500个元素，升序排列，现在在这20*500个数中找出排名前500的数。
转载请注明出处
方法思路分析
笔者想到3中方法，水平有限，欢迎拍砖指导，有更好的方法欢迎评论留言。
直接暴力求解，将20个数组合并，然后排序，取出500个数
使用归并。 对于排好序的 序列，我们要注意使用归并。
先将第1个和第2个归并，得到500个数据（注意，我们不是归并得到100个数）。然后再加结果和第3个归并，得到500个数据，再与第4个归并，等等。
网上的方法，就是堆。保持一个20的堆，然后先将每个数组的第1个数入堆。
20个元素的堆一直保持容量为20个，20个数组的最小元素可以将20个数组的第0个元素入堆，最小堆的性质，顶点为最小值。这时候得到了500个结果里的第0个结果。然后再把下一个元素入20个元素的堆，堆插入的时候会保持性质不变，最小元素依然在顶点。再取出20个元素的顶点，得到500个结果里的第1个结果。
假设 [1,3,4,5,6]
[2,3,4,5,6] [3,4,5,6,7]
最小的是比较 1 2 3 得到1
第2小的是将刚才的1替换为后面的元素3 再加上刚才的元素2 3，得到2
注意这儿需要保持数来自于哪个数组，以及其在数组里的位置
Integer[] allData = new Integer[20 * 500];
int a = 0;
for (int ii = 0; ii & rowS ii++) {
for (int i = 0; i & columnS i++) {
allData[a++] = data[ii][i];
Arrays.sort(allData);
Integer[] result1 = Arrays.copyOfRange(allData, 0, columnSize);
System.out.println("method 1 result:
" + Arrays.toString(result1));
先定义一个 merge 函数，从两个数组里面得到前500个数据。
数组的长度，假定 first 和 second 的长度均为 n
* 返回一个长度为 n 的数组
private static Integer[] merge(Integer[] first, Integer[] second, int n) {
Integer[] temp = new Integer[n];
int f = 0;
int s = 0;
int i = 0;
while (i != n && f &= n && s &= n) {
if (first[f] & second[s]) {
temp[i++] = first[f++];
temp[i++] = second[s++];
下来是总的归并代码
// 方法2，归并，先归并前两个数组，取前500个数据。将得到的结果再与第3个归并，重复
// 考虑一下,20个数组先两两归并，得到10个；10个再两两归并，得到5个。等等，直到最后1个
// 但这样归并的次数和从前往后两两归并的次数是一样的？所以还是 上述的从前往后好了
// 复杂度是 19*500
Integer[] result2 = data[0];
for (int i = 1; i & rowS i++) {
result2 = merge(result2, data[i], columnSize);
System.out.println("method 2 result:
" + Arrays.toString(result2));
System.out.println("result1 equals result2: " + Arrays.equals(result1, result2));
定义一个最小堆，有插入和删除方法
* 最小堆和堆排序, 最小堆，顶点的元素是最小值， 根据《Java 语言程序设计 进阶篇》 p83 改写， 书上是最大堆. 堆排序
* 将元素都存入最小堆中，从最小堆里面每次取出顶点元素
class MinHeap&E extends Comparable& {
public static &E extends Comparable& void heapSort(E[] array) {
MinHeap&E& heap = new MinHeap&E&();
for (int i = 0; i & array. i++) {
heap.add(array[i]);
System.out.println("Debug: heap is
" + heap);
for (int i = 0; i & array. i++) {
array[i] = heap.removeTop();
private ArrayList&E& data = new ArrayList&E&();
public MinHeap() {
* 增加一个新元素，步骤是 1. 先把元素插入到 list 的末尾 2. 比较末尾元素和它的父元素，若小于，交换两者 3.
* 重复上述步骤，直到到顶点位置或者子元素大于父元素 4. 不一定要遍历堆所有的元素，达到堆的性质后会提前结束
public void add(E array) {
data.add(array);
int child = data.size() - 1;
int parent = (child - 1) / 2;
while (child & 0) {
if (data.get(parent).compareTo(array) & 0) {
data.set(child, data.get(parent));
data.set(parent, array);
parent = (child - 1) / 2;
* 删除顶点处的元素，步骤是： 1. 把末尾的元素复制到顶点处 2. 然后比较此时顶点的值和左右子树，保持最小堆的性质 3.
* 交换顶点和左右子树较小的值 4. 重复上述步骤，直到已经成了最小堆或者遍历完 5. 注意可能存在左子树存在，右子树不存在情况 6.
* 不一定要遍历堆所有的元素，达到堆的性质后会提前结束
* 返回被删除的元素
public E removeTop() {
if (data.isEmpty())
return null;
E removed = data.get(0);
E last = data.get(data.size() - 1);
data.set(0, last);
data.remove(data.size() - 1);
int parent = 0;
int leftChild = parent * 2 + 1;
int rightChild = parent * 2 + 2;
while (leftChild &= data.size() - 1) {
int minIndex = leftC
if (rightChild &= data.size() - 1) {
if (data.get(rightChild).compareTo(data.get(leftChild)) & 0) {
minIndex = rightC
if (data.get(minIndex).compareTo(last) & 0) {
data.set(parent, data.get(minIndex));
data.set(minIndex, last);
parent = minI
leftChild = parent * 2 + 1;
rightChild = parent * 2 + 2;
public String toString() {
return data.toString();
为了能够记录堆里的元素来自哪个数组，以及在数组里的位置，我们使用一个内部类
class DataWithSource implements Comparable&DataWithSource& {
private Integer value;
private Integer comeF
public DataWithSource(Integer value, Integer comeFrom, Integer index) {
this.value = value;
this.comeFrom = comeF
this.index =
public Integer getComeFrom() {
return comeF
public Integer getValue() {
return value;
public void setValue(Integer value) {
this.value = value;
public Integer getIndex() {
public void setIndex(Integer index) {
this.index =
public int compareTo(DataWithSource o) {
return this.value.compareTo(o.value);
下面是方法3的代码
public static void main(String[] args) {
Random r = new Random();
int rowSize = 20;
int columnSize = 500;
Integer[][] data = new Integer[rowSize][columnSize];
for (int ii = 0; ii & rowS ii++) {
for (int i = 0; i & columnS i++) {
data[ii][i] = r.nextInt(1600);
Arrays.sort(data[ii]);
Integer[] allData = new Integer[20 * 500];
int a = 0;
for (int ii = 0; ii & rowS ii++) {
for (int i = 0; i & columnS i++) {
allData[a++] = data[ii][i];
Arrays.sort(allData);
Integer[] result1 = Arrays.copyOfRange(allData, 0, columnSize);
System.out.println("method 1 result:
" + Arrays.toString(result1));
Integer[] result2 = data[0];
for (int i = 1; i & rowS i++) {
result2 = merge(result2, data[i], columnSize);
System.out.println("method 2 result:
" + Arrays.toString(result2));
System.out.println("result1 equals result2: " + Arrays.equals(result1, result2));
Integer[] result3 = new Integer[500];
MinHeap&DataWithSource& heap = new MinHeap&DataWithSource&();
for (int i = 0; i & rowS i++) {
DataWithSource d = new DataWithSource(data[i][0], i, 0);
heap.add(d);
int num = 0;
while (num & columnSize) {
DataWithSource d = heap.removeTop();
result3[num++] = d.getValue();
d.setValue(data[d.getComeFrom()][d.getIndex() + 1]);
d.setIndex(d.getIndex() + 1);
heap.add(d);
System.out.println("method 3 result:
" + Arrays.toString(result3));
System.out.println("result2 equals result3: " + Arrays.equals(result2, result3));
method 1 result:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 48, 48, 48, 49, 49, 49, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 68, 68, 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 75, 75, 76, 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 79, 79, 79]
method 2 result:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 48, 48, 48, 49, 49, 49, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 68, 68, 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 75, 75, 76, 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 79, 79, 79]
result1 equals result2: true
method 3 result:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 33, 33, 34, 34, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 46, 47, 47, 48, 48, 48, 49, 49, 49, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 54, 54, 54, 54, 54, 54, 54, 54, 55, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 68, 68, 68, 68, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 70, 70, 70, 70, 71, 71, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 72, 72, 73, 73, 73, 73, 73, 74, 74, 74, 74, 74, 74, 74, 75, 75, 76, 76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 78, 79, 79, 79]
result2 equals result3: true
如果文章对您有帮助，不妨捐赠一注彩票钱^=^
支付宝二维码
微信二维码
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：184006次
积分：5435
积分：5435
排名：第3846名
原创：196篇
评论：91条一个简单的问题，这道题是不是题目有问题呐_初中物理吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：45,890贴子：
一个简单的问题，这道题是不是题目有问题呐收藏
第二小问，题目里根本没说甲球要不要拿出啊？，那怎么算相等与否
初中物理-新东方聚20年教学教研精华,雄厚的师资力量,帮助你快速提分!初中物理-上海新东方中学:精细化课程设置,满足学员不同阶段的学习需求!轻松入名校!
显然得拿出来，单独在里面才能比较，题目有点没说明白，把先后改称分别就好了
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或七年级数学(上)有理数的混合运算练习题40道(带答案)_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
七年级数学(上)有理数的混合运算练习题40道(带答案)
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢20以内的加减法练习题100道_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
20以内的加减法练习题100道
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩15页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢