有一类面试题，既可以考察工程师算法、也可以兼顾实践应用、甚至创新思维，这些题目便是好的题目，有区分度表现为可以有一般解，也可以有最优解。最近就发现了一个这样的好题目，拿出来晒一晒。
1 题目 原文：
There is an array of 10000000 different int numbers. Find out its largest 100 elements. The implementation should be optimized for executing speed.
翻译：
有一个长度为1000万的int数组，各元素互不重复。如何以最快的速度找出其中最大的100个元素？
2 分析与解 （接下来的算法均以Java语言实现。）
首先，第一个冒出来的想法是——排序。各种排序算法对数组进行一次sort，然后limit出max的100个即可，时间复杂度为O(nLogN)。
2.1 堆排序思路 我以堆排序来实现这个题目，这样可以使用非常少的内存空间，始终维护一个100个元素大小的最小堆，堆顶int[0]即是100个元素中最小的，插入一个新的元素的时候，将这个元素和堆顶int[0]进行交换，也就是淘汰掉堆顶，然后再维护一个最小堆，使int[0]再次存储最小的元素，循环往复，不断迭代，最终剩下的100个元素就是结果，该算法时间复杂度仍然是O(nLogN)，优点在于节省内存空间，算法时间复杂度比较理想，平均耗时400ms。
代码实现如下，
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 |
import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * Implementation of finding top 100 elements out of a huge int array. <br> * * There is an array of 10000000 different int numbers. Find out its largest 100 * elements. The implementation should be optimized for executing speed. <br> * * Note: This is the third version of implementation, this time I make the best out * of the heap sort algorithm by using a minimum heap. The heap maintains the top biggest * numbers that guarantees the minimum number is removed every time a new number is added * to the heap. It saves memory usage to the limit by just using an array which size is 101 * and a few temp elements. However, the performance is not as good as the bit map way but * better than the multiple thread way. * * @author zhangxu04 */ public class FindTopElements3 { private static final int ARRAY_LENGTH = 10000000; // big array length public static void main(String[] args) { FindTopElements3 fte = new FindTopElements3(); // Get a array which is not in order and elements are not duplicate int[] array = getShuffledArray(ARRAY_LENGTH); // Find top 100 elements and print them by desc order in the console long start = System.currentTimeMillis(); fte.findTop100(array); long end = System.currentTimeMillis(); System.out.println("Costs " + (end - start) + "ms"); 师算法、也可以兼顾实践应用、甚至创新思维，这些题目便是好的题目，有区分度表现为可以有一般解，也可以有最优解。最近就发现了一个这样的好题目，拿出来晒一晒。
1 题目 原文：
翻译： 有一个长度为1000万的int数组，各元素互不重复。如何以最快的速度找出其中最大的100个元素？ 2 分析与解 （接下来的算法均以Java语言实现。）首先，第一个冒出来的想法是——排序。各种排序算法对数组进行一次sort，然后limit出max的100个即可，时间复杂度为O(nLogN)。 2.1 堆排序思路 我以堆排序来实现这个题目，这样可以使用非常少的内存空间，始终维护一个100个元素大小的最小堆，堆顶int[0]即是100个元素中最小的，插入一个新的元素的时候，将这个元素和堆顶int[0]进行交换，也就是淘汰掉堆顶，然后再维护一个最小堆，使int[0]再次存储最小的元素，循环往复，不断迭代，最终剩下的100个元素就是结果，该算法时间复杂度仍然是O(nLogN)，优点在于节省内存空间，算法时间复杂度比较理想，平均耗时400ms。 代码实现如下，
|
