从十亿个数中选定十万个最大数的最快算法
从十亿个数中选出十万个最大数的最快算法
还有一题：设计一个数据结构使可以像数组一样随意访问链表的元素
------解决方案--------------------
第一题：十亿个数中选出十万个最大数
方式1: O(N * Log M)： 用最小堆。 不断的往最小堆中插入数字即可。 每当堆的元素超过十万个时， 只需要将堆顶元素弹出即可。
方式2：O(N) 假定数字范围为 0 -> 2^32-1 即32位无符号整数，可用如下方式。
需要对数组做两次扫描。
设一个计数器数组 Count[65536]
第一次扫描： Count[A[i] >> 16] ++。 以数字的高16位作为下标，直接对计数器 + 1。
如此一来可以统计出 各个 高16位的个数。 对计数器从高到低进行一遍扫描，并进行累加就可以得出 排在第 10万的数字它的高 16位是多少，设为H。
计数器全部清0，并进行第二次扫描。 若 a[i] 的高 16位 大于 H ，则该数字肯定是最大的10万个里面的。 若a[i] 的高16位 小于 H，则直接忽略。 若等于H， 则将其低 16位 作为下标对计数器 + 1. 即：Count[a[i] & 0xFFFF] ++。
第二次扫描结束后， 看看还缺多少个数字， 对计数器也再做一次 从高到低的扫描，直接根据 高16位的H 以及计数器的低16位构造即可。
第二题： 据我所知好像没有可以支持随机访问的链表，顶多是通过算法来进行加速。
------解决方案--------------------
可用"线性时间选择",在O(n)时间内解决该问题.算法:
STEP1) 用线性时间选择找出第 M 大的数X;耗时 O(N)
STEP2) 扫描所有的值,只要大于等于 X,就输出,耗时 O(N)
------解决方案--------------------
可用"线性时间选择",在O(n)时间内解决该问题.算法:
STEP1) 用线性时间选择找出第 M 大的数X;耗时 O(N)
STEP2) 扫描所有的值,只要大于等于 X,就输出,耗时 O(N)
-----------------------------------------------------
+1
还有一题：设计一个数据结构使可以像数组一样随意访问链表的元素
------解决方案--------------------
第一题：十亿个数中选出十万个最大数
方式1: O(N * Log M)： 用最小堆。 不断的往最小堆中插入数字即可。 每当堆的元素超过十万个时， 只需要将堆顶元素弹出即可。
方式2：O(N) 假定数字范围为 0 -> 2^32-1 即32位无符号整数，可用如下方式。
需要对数组做两次扫描。
设一个计数器数组 Count[65536]
第一次扫描： Count[A[i] >> 16] ++。 以数字的高16位作为下标，直接对计数器 + 1。
如此一来可以统计出 各个 高16位的个数。 对计数器从高到低进行一遍扫描，并进行累加就可以得出 排在第 10万的数字它的高 16位是多少，设为H。
计数器全部清0，并进行第二次扫描。 若 a[i] 的高 16位 大于 H ，则该数字肯定是最大的10万个里面的。 若a[i] 的高16位 小于 H，则直接忽略。 若等于H， 则将其低 16位 作为下标对计数器 + 1. 即：Count[a[i] & 0xFFFF] ++。
第二次扫描结束后， 看看还缺多少个数字， 对计数器也再做一次 从高到低的扫描，直接根据 高16位的H 以及计数器的低16位构造即可。
第二题： 据我所知好像没有可以支持随机访问的链表，顶多是通过算法来进行加速。
------解决方案--------------------
可用"线性时间选择",在O(n)时间内解决该问题.算法:
STEP1) 用线性时间选择找出第 M 大的数X;耗时 O(N)
STEP2) 扫描所有的值,只要大于等于 X,就输出,耗时 O(N)
------解决方案--------------------
可用"线性时间选择",在O(n)时间内解决该问题.算法:
STEP1) 用线性时间选择找出第 M 大的数X;耗时 O(N)
STEP2) 扫描所有的值,只要大于等于 X,就输出,耗时 O(N)
-----------------------------------------------------
+1