10w个数,选出最大的100个,怎么做?时间复杂度是多少?

回答思路

1. 能给出至少一种正确解法,如维护大小为100的最小堆
2. 分析最小堆解法的时间复杂度为O(n log k)
3. 对比其他方法如全排序O(n log n)与快排partition优化的期望O(n)
4. 能说明各自适用场景,理解堆解法空间为O(k)
5. 不混淆k与n的复杂度,能清楚表达常数因子优化