首页 文章

编写一个程序，从10亿个数字的数组中找出100个最大的数字

提问于
浏览 次
294

我最近参加了一次采访，我被问到“编写一个程序，从10亿个数字中找出100个最大的数字 . ”

我只能给出一个强力解决方案，即以O（nlogn）时间复杂度对数组进行排序，并取最后100个数字 .

Arrays.sort(array);

面试官正在寻找更好的时间复杂性，我尝试了其他一些解决方案，但未能回答他 . 有更好的时间复杂度解决方案吗？

algorithm sorting

30 回答

  • 0

    你可以迭代需要O（n）的数字

    只要找到大于当前最小值的值，就将新值添加到大小为100的循环队列中 .

    该循环队列的最小值是您的新比较值 . 继续添加到该队列 . 如果已满，请从队列中提取最小值 .

    回复于
  • 16
    Time ~ O(100 * N)
Space ~ O(100 + N)

    • 创建一个100空插槽的空列表

    • 对于输入列表中的每个数字：

    • 如果数字小于第一个，请跳过

    • 否则用这个号码替换它

    • 然后，通过相邻交换推送数字;直到它小于下一个

    • 返回列表

    Note: 如果 log(input-list.size) + c < 100 ，则最佳方式是对输入列表进行排序，然后拆分前100项 .

    回复于
  • 322

    每当遇到大于队列中最小数字（队列头部）的数字时，您可以保留100个最大数字的优先级队列，遍历十亿个数字，删除队列的头部并添加新的数字到队列 .

    如Dev所述 EDIT: ，使用堆实现优先级队列，插入队列的复杂性为 O(logN)

    在最坏的情况下，你得到的 billionlog2(100) 好于 billion log2(billion)

    通常，如果您需要来自一组N个数字的最大K数，则复杂度为 O(NlogK) 而不是 O(NlogN) ，当K与N相比非常小时，这可能非常重要 .

    EDIT2:

    该算法的预期时间非常有趣，因为在每次迭代中，插入可能会也可能不会发生 . 第i个数字被插入队列的概率是随机变量大于来自同一分布的随机变量的概率（前k个数字被自动添加到队列中） . 我们可以使用订单统计（参见link）来计算这个概率 . 例如，假设从 {0, 1} 中均匀地随机选择数字，第（i-K）个数字（i个数字中）的期望值是 (i-k)/i ，并且随机变量大于该值的机会是 1-[(i-k)/i] = k/i .

    因此，预期的插入次数是：

    enter image description here

    预计运行时间可表示为：

    enter image description here

    （ k 生成具有第一个 k 元素的队列的时间，然后 n-k 比较，以及如上所述的预期插入次数，每个平均 log(k)/2 时间）

    请注意，当 N 与 K 相比非常大时，此表达式更接近 n 而不是 NlogK . 这有点直观，就像在问题的情况下，即使在10000次迭代之后（与十亿次相比非常小），数字插入队列的可能性非常小 .

    回复于
  • 16

    如果在面试中询问，我认为面试官可能希望看到您的问题解决过程，而不仅仅是您对算法的了解 .

    描述很一般，所以也许你可以问他这些数字的范围或含义，以使问题清楚 . 这样做可能会给面试官留下深刻印象 . 例如，如果这些数字代表人们更容易解决问题 . 假设没有人活着超过200，你可以使用大小为200（可能是201）的int数组来计算一次迭代中具有相同年龄的人数 . 这里的指数意味着年龄 . 在此之后，找到100个最大的数字是一块蛋糕 . 顺便说一句，这个算法被称为 counting sort .

    无论如何，在面试中使问题更具体和更清晰对你有好处 .

    回复于
  • 71

    我意识到这是用'算法'标记的，但是会抛出一些其他的选项，因为它可能也应该标记为'面试' .

    10亿个数字的来源是什么？如果它是一个数据库，那么'通过值desc limit 100从表顺序中选择值'可以很好地完成工作 - 可能存在方言差异 .

    这是一次性的，还是会重复的？如果重复，多久一次？如果它是一次性的并且数据在文件中，那么'cat srcfile |排序（根据需要选择）| head -100'会让你快速做有成效的工作，当你的计算机处理这个微不足道的家务时，你会得到报酬 .

    如果重复，你会建议采取任何体面的方法来获得初始答案并存储/缓存结果，这样你就可以连续报告前100名 .

    最后，有这种考虑 . 您是否正在寻找一份入门级的工作并与一位令人讨厌的经理或未来的同事面谈？如果是这样，那么你可以抛弃描述相关技术优缺点的各种方法 . 如果您正在寻找更多的管理工作，那么就像经理那样关注解决方案的开发和维护成本，然后说“非常感谢”并离开，如果这是面试官想要关注的话CS琐事 . 他和你在那里不太可能有太大的进步潜力 .

    在接下来的采访中祝你好运 .

    回复于
  • -1

    您可以使用Quick select algorithm在（按顺序）索引[十亿-101]中查找数字，然后迭代数字并查找与该数字相比的数字 .

    array={...the billion numbers...} 
result[100];

pivot=QuickSelect(array,billion-101);//O(N)

for(i=0;i<billion;i++)//O(N)
   if(array[i]>=pivot)
      result.add(array[i]);

    This algorithm Time is: 2 X O(N) = O(N) (Average case performance)

    像 Thomas Jungblut 建议的第二个选项是：

    使用Heap构建MAX堆将采用O（N），然后前100个最大数字将位于堆的顶部，您只需要将它们从堆中取出（100 X O（Log（N）） .

    This algorithm Time is:O(N) + 100 X O(Log(N)) = O(N)

    回复于
  • 0

    我对此的立即反应是使用堆，但有一种方法可以使用QuickSelect，而无需在任何时候保留所有输入值 .

    创建一个大小为200的数组，并用前200个输入值填充它 . 运行QuickSelect并丢弃低100，留下100个空闲位置 . 读入接下来的100个输入值并再次运行QuickSelect . 继续，直到您以100个批次运行整个输入 .

    最后，您有前100个值 . 对于N值，您大约运行QuickSelect N / 100次 . 每个Quickselect的成本约为常数的200倍，因此总成本是某些常数的2N倍 . 这看起来与我输入的大小呈线性关系，无论我在这个解释中硬接线为100的参数大小 .

    回复于
  • 4

    尽管另一个quickselect解决方案已被低估，但事实仍然是quickselect将比使用100号队列更快地找到解决方案 . 在比较方面，Quickselect的预期运行时间为2n o（n） . 一个非常简单的实现将是

    array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
  if(array[i]>r)
     add array[i] to result

    这将平均进行3n o（n）次比较 . 此外，使用quickselect将在最右边的100个位置留下阵列中最大的100个项目这一事实可以提高效率 . 事实上，运行时间可以提高到2n o（n） .

    问题在于这是预期的运行时间，而不是最坏的情况，但是通过使用适当的枢轴选择策略（例如，随机挑选21个元素，并选择那些21的中位数作为枢轴），那么比较的数量可以是对于任意小的常数c，保证最高概率为（2 c）n .

    实际上，通过使用优化的采样策略（例如，随机采样sqrt（n）元素，并选择第99百分位数），对于任意小的c，运行时间可以降低到（1 c）no（n）（假设K，要选择的元素数是o（n）） .

    另一方面，使用大小为100的队列将需要O（log（100）n）比较，并且100的log基数2约等于6.6 .

    如果我们从更大的抽象意义上考虑这个问题，从大小为N的数组中选择最大的K元素，其中K = o（N）但K和N都变为无穷大，那么quickselect版本的运行时间将是O（N）和队列版本将是O（N log K），因此在这个意义上，quickselect也渐近优越 .

    在评论中，有人提到队列解决方案将在随机输入的预期时间N K log N内运行 . 当然，除非问题明确说明，否则随机输入假设永远不会有效 . 可以使队列解决方案以随机顺序遍历数组，但这将导致对随机数生成器的N次调用的额外成本以及置换整个输入数组或者分配长度为N的新数组，其中包含随机指数 .

    如果问题不允许你移动原始数组中的元素，并且分配内存的成本很高，那么复制数组不是一个选项，这是另一回事 . 但严格来说，就运行时间而言，这是最好的解决方案 .

    回复于
  • 0

    取出十亿分之一的前100个数字并对它们进行排序 . 现在只迭代十亿，如果源数高于100的最小值，则按排序顺序插入 . 你最终得到的是与集合大小相比更接近O（n）的东西 .

    回复于
  • -1

    两种选择：

    （1）堆（priorityQueue）

    保持大小为100的最小堆 . 遍历阵列 . 一旦元素小于堆中的第一个元素，替换它 .

    InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)

    （2）Map-reduce模型 .

    这与hadoop中的字数例子非常相似 . Map 作业：计算每个元素的频率或时间 . 减少：获得顶级K元素 .

    通常，我会给招聘人员两个答案 . 给他们任何他们喜欢的 . 当然， Map 缩减编码会很费力，因为你必须知道每个确切的参数 . 练习它没有坏处 . 祝好运 .

    回复于
  • 133

    一个非常简单的解决方案是迭代数组100次 . 这是 O(n) .

    每次拉出最大数字（并将其值更改为最小值，以便在下一次迭代中看不到它，或者跟踪先前答案的索引（通过跟踪原始数组可能具有的索引）多个相同的数字）） . 经过100次迭代后，您拥有100个最大的数字 .

    回复于
  • 1

    我看到很多O（N）讨论，所以我提出了一些不同的思想练习 .

    是否有关于这些数字性质的已知信息？如果它本质上是随机的，那就不要再进一步看看其他答案了 . 你不会得到比他们更好的结果 .

    然而！查看列表填充机制是否以特定顺序填充该列表 . 它们是否处于明确定义的模式中，您可以确定地知道在列表的某个区域或某个区间内可以找到最大数量的数字？可能有一种模式 . 如果是这样的话，例如，如果它们保证在某种正常分布中，中间有特征驼峰，则在定义的子集中总是有重复的上升趋势，在数据中间的某个时间T有一个长时间的峰值设置可能是内幕交易或设备故障的发生率，或者可能只是在每个第N个数字中出现“峰值”，就像灾难发生后的力量分析一样，您可以减少必须检查的记录数量显著 .

    无论如何，还有一些值得思考的东西 . 也许这会帮助你给未来的面试官一个深思熟虑的答案 . 我知道如果有人在回答这样的问题时问我这样的问题，我会留下深刻的印象 - 它会告诉我他们正在考虑优化 . 只是意识到可能并不总是有可能进行优化 .

    回复于
  • 0

    受到@ron的启发teller的回答，这是一个准确做你想做的准系统C程序 .

    #include <stdlib.h>
#include <stdio.h>

#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100

int 
compare_function(const void *first, const void *second)
{
    int a = *((int *) first);
    int b = *((int *) second);
    if (a > b){
        return 1;
    }
    if (a < b){
        return -1;
    }
    return 0;
}

int 
main(int argc, char ** argv)
{
    if(argc != 2){
        printf("please supply a path to a binary file containing 1000000000"
               "integers of this machine's wordlength and endianness\n");
        exit(1);
    }
    FILE * f = fopen(argv[1], "r");
    if(!f){
        exit(1);
    }
    int top100[N_TOP_NUMBERS] = {0};
    int sorts = 0;
    for (int i = 0; i < TOTAL_NUMBERS; i++){
        int number;
        int ok;
        ok = fread(&number, sizeof(int), 1, f);
        if(!ok){
            printf("not enough numbers!\n");
            break;
        }
        if(number > top100[0]){
            sorts++;
            top100[0] = number;
            qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
        }

    }
    printf("%d sorts made\n"
    "the top 100 integers in %s are:\n",
    sorts, argv[1] );
    for (int i = 0; i < N_TOP_NUMBERS; i++){
        printf("%d\n", top100[i]);
    }
    fclose(f);
    exit(0);
}

    在我的机器上（带有快速SSD的核心i3）需要25秒，1724种 . 我为此次运行生成了一个带 dd if=/dev/urandom/ count=1000000000 bs=1 的二进制文件 .

    显然，从磁盘一次只读取4个字节存在性能问题，但这是例如 . 从好的方面来说，只需要很少的内存 .

    回复于
  • 1

    最简单的解决方案是扫描十亿个数字的大数组，并将目前为止发现的100个最大值保存在一个小数组缓冲区中而不进行任何排序，并记住该缓冲区的最小值 . 首先，我认为这种方法是由fordprefect提出的，但在评论中他说他假设100号数据结构被实现为堆 . 每当发现一个较大的新数字时，缓冲区中的最小值将被找到的新值覆盖，并再次搜索缓冲区的当前最小值 . 如果十亿数组中的数字随机分布在大多数时间，则将来自大数组的值与小数组的最小值进行比较并丢弃 . 只有极小数量的数值才能将值插入小数组中 . 因此，可以忽略操纵保持较小数字的数据结构的差异 . 对于少量元素，很难确定优先级队列的使用是否实际上比使用我的天真方法更快 .

    我想估计扫描10 ^ 9元素阵列时小100元素阵列缓冲区中的插入数 . 程序扫描此大型数组的前1000个元素，并且必须在缓冲区中插入最多1000个元素 . 缓冲区包含扫描的1000个元素中的100个元素，即扫描的元素的0.1 . 因此，我们假设大数组中的值大于缓冲区的当前最小值的概率约为0.1 . 这样的元素必须插入缓冲区中 . 现在程序扫描大阵列中的下一个10 ^ 4个元素 . 因为每次插入新元素时缓冲区的最小值都会增加 . 我们估计大于当前最小值的元素比率约为0.1，因此要插入0.1 * 10 ^ 4 = 1000个元素 . 实际上，插入缓冲区的预期元素数量会更少 . 在扫描该10 ^ 4个元素之后，缓冲区中数字的分数将是到目前为止扫描的元素的约0.01 . 因此，当扫描下一个10 ^ 5数字时，我们假设将在缓冲区中插入不超过0.01 * 10 ^ 5 = 1000的数字 . 继续这个论证，我们在扫描大阵列的1000个10 ^ 4 10 ^ 5 ... 10 ^ 9~10 ^ 9个元素后插入了大约7000个值 . 因此，当扫描具有10 ^ 9个随机大小元素的数组时，我们期望缓冲区中的插入不超过10 ^ 4（= 7000个向上舍入） . 每次插入缓冲区后，必须找到新的最小值 . 如果缓冲区是一个简单的数组，我们需要进行100次比较才能找到新的最小值 . 如果缓冲区是另一个数据结构（如堆），我们需要至少1次比较才能找到最小值 . 为了比较大数组的元素，我们需要进行10 ^ 9次比较 . 总而言之，当使用数组作为缓冲区时，我们需要大约10 ^ 9 100 * 10 ^ 4 = 1.001 * 10 ^ 9比较，当使用其他类型的数据结构（如堆）时，至少需要1.000 * 10 ^ 9比较 . 因此，如果性能由比较次数确定，则使用堆只会带来0.1％的增益 . 但是，在100个元素堆中插入元素和替换100个元素数组中的元素并找到新的最小值之间的执行时间有何不同？

    • 在理论层面：插入堆需要多少次比较 . 我知道它是O（log（n））但是常数因子有多大？一世

    • 在机器级别：缓存和分支预测对堆插入的执行时间和数组中的线性搜索有何影响 .

    • 在实现级别：库或编译器提供的堆数据结构中隐藏了哪些额外成本？

    我认为在尝试估计100个元素堆或100个元素数组的性能之间的真正差异之前，这些是必须回答的一些问题 . 因此，进行实验并衡量真实表现是有意义的 .

    回复于
  • 0
    Although in this question we should search for top 100 numbers, I will 
 generalize things and write x. Still, I will treat x as constant value.

    Algorithm Biggest x elements from n:

    我将调用返回值 LIST . 它是一组x元素（在我看来应该是链表）

    • 第一个x元素取自池"as they come"并在LIST中排序（这是在恒定时间内完成的，因为x被视为常量--O（x log（x））时间）

    • 对于接下来的每个元素，我们检查它是否大于LIST中的最小元素，如果是，我们弹出最小的元素并将当前元素插入LIST . 由于这是有序列表，因此每个元素应该以对数时间（二进制搜索）找到它的位置，并且由于它是有序列表插入不是问题 . 每一步都是在恒定时间内完成的（O（log（x））时间） .

    那么，最糟糕的情况是什么？

    x log（x）（n-x）（log（x）1）= nlog（x）n - x

    所以这是最坏情况下的O（n）时间 . 1是检查LIST中的数字是否大于最小值 . 平均情况的预期时间将取决于这些n个元素的数学分布 .

    Possible improvements

    对于最坏的情况，这个算法可以略微改进，但恕我直言（我不能证明这个说法）会降低平均行为 . 渐近行为将是相同的 .

    该算法的改进是我们不会检查元素是否大于最小值 . 对于每个元素，我们将尝试插入它，如果它小于最小值，我们将忽略它 . 虽然如果我们只考虑我们将遇到的最坏情况，这听起来很荒谬

    x log（x）（n-x）log（x）= nlog（x）

    操作 .

    对于这个用例，我没有看到任何进一步的改进 . 然而你必须问问自己 - 如果我必须做的比log（n）次和不同的x-es更多？显然我们会在O（n log（n））中对该数组进行排序，并在需要时使用我们的x元素 .

    回复于
  • 4

    只用一行C代码就可以用N log（100）复杂度（而不是N log N）来回答这个问题 .

    std::vector<int> myvector = ...; // Define your 1 billion numbers. 
                                 // Assumed integer just for concreteness 
 std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());

    最后的答案是一个向量，其中前100个元素保证是你阵列的100个最大数字，而其余元素是无序的

    C STL（标准库）对于这类问题非常方便 .

    注意：我并不是说这是最佳解决方案，但它可以保存您的面试 .

    回复于
  • 1

    简单的解决方案是使用优先级队列，将前100个数字添加到队列中并跟踪队列中的最小数字，然后迭代其他十亿个数字，每次我们找到一个大于最大数字的数字在优先级队列中，我们删除最小的数字，添加新的数字，并再次跟踪队列中的最小数字 .

    如果这些数字是随机排列的，那么这将很有效，因为当我们迭代十亿个随机数时，到目前为止，下一个数字在100个最大数量中是非常罕见的 . 但数字可能不是随机的 . 如果数组已按升序排序，那么我们将始终将元素插入优先级队列 .

    所以我们首先从阵列中挑出100,000个随机数 . 为了避免可能很慢的随机访问，我们添加了400个连续250个连续数字的随机组 . 通过随机选择，我们可以确定剩下的数字中只有极少数位于前100位，因此执行时间将非常接近于将十亿个数字与某个最大值进行比较的简单循环 .

    回复于
  • 0

    查找十亿个数字中的前100个最好使用100个元素的min-heap .

    首先使用遇到的前100个数字填充最小堆 . min-heap将存储根（顶部）中前100个数字中最小的一个 .

    现在，当您继续使用其余数字时，只将它们与根（100中的最小值）进行比较 .

    如果遇到的新数字大于min-heap的根，则用该数字替换root，否则忽略它 .

    作为在min-heap中插入新数字的一部分，堆中的最小数字将位于顶部（根） .

    一旦我们完成了所有数字，我们将在最小堆中拥有最大的100个数字 .

    回复于
  • 32

    我已经用Python编写了一个简单的解决方案，以防任何人感兴趣 . 它使用 bisect 模块和一个保持排序的临时返回列表 . 这类似于优先级队列实现 .

    import bisect

def kLargest(A, k):
    '''returns list of k largest integers in A'''
    ret = []
    for i, a in enumerate(A):
        # For first k elements, simply construct sorted temp list
        # It is treated similarly to a priority queue
        if i < k:
            bisect.insort(ret, a) # properly inserts a into sorted list ret
        # Iterate over rest of array
        # Replace and update return array when more optimal element is found
        else:
            if a > ret[0]:
                del ret[0] # pop min element off queue
                bisect.insort(ret, a) # properly inserts a into sorted list ret
    return ret

    使用100,000,000个元素和最坏情况输入，这是一个排序列表：

    >>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
 99999996, 99999997, 99999998, 99999999]

    花了大约40秒来计算100,000,000个元素，所以我很害怕这个10亿元 . 为了公平起见，我正在为它提供最坏情况的输入（具有讽刺意味的是已经排序的数组） .

    回复于
  • 1

    复杂性是O（N）

    首先创建一个100 int的数组，初始化该数组的第一个元素作为N值的第一个元素，用另一个变量跟踪当前元素的索引，称之为CurrentBig

    迭代N值

    if N[i] > M[CurrentBig] {

M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)

CurrentBig++;      ( go to the next position in the M array)

CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)

M[CurrentBig]=N[i];    ( pick up the current value again to use it for the next Iteration of the N array)

}

    完成后，从CurrentBig打印M数组100次模数100 :-)对于学生：确保代码的最后一行在代码退出之前不会胜过有效数据

    回复于
  • 0

    另一个O（n）算法 -

    该算法通过消除找到最大的100

    考虑二进制表示中的所有百万个数字 . 从最重要的位开始 . 查找MSB是否为1可以通过布尔运算乘以适当的数来完成 . 如果这些百万中超过100个1，则用零消除其他数字 . 现在剩下的数字继续下一个最重要的位 . 保留消除后剩余数量的计数，并且只要该数字大于100，就继续进行 .

    主要的布尔操作可以在GPU上并行完成

    回复于
  • 10

    我会发现谁有时间将十亿个数字放入一个数组并解雇他 . 必须为政府工作 . 至少如果你有一个链表，你可以在中间插入一个数字而不用移动五十亿来腾出空间 . 更好的Btree允许二进制搜索 . 每次比较都消除了总数的一半 . 哈希算法允许您像棋盘一样填充数据结构，但对稀疏数据不太好 . 因为你最好的办法是拥有一个100个整数的解决方案数组，并跟踪解决方案数组中的最小数字，这样当你在原始数组中遇到更高的数字时就可以替换它 . 你必须查看原始数组中的每个元素，假设它没有排序开始 .

    回复于
  • 0

    你可以在 O(n) 时间内完成 . 只需遍历列表并跟踪您在任何给定点看到的100个最大数字以及该组中的最小值 . 当你发现一个比你的十分之一更大的新数字，然后更换它并更新100的新最小值（可能需要100的恒定时间来确定每次这样做，但这不会影响整体分析） .

    回复于
  • 0

    • 使用nth-element获取第100个元素O（n）

    • 第二次迭代但只迭代一次并输出大于此特定元素的每个元素 .

    特别请注意 . 第二步可能很容易并行计算！当你需要一百万个最大的元素时，它也会很有效 .

    回复于
  • 5

    这是来自谷歌或其他一些行业巨头的问题 . 可能以下代码是您的面试官所期望的正确答案 . 时间成本和空间成本取决于输入数组中的最大数量 . 对于32位int数组输入，最大空间成本为4 * 125M字节，时间成本为5 * 10亿 .

    public class TopNumber {
    public static void main(String[] args) {
        final int input[] = {2389,8922,3382,6982,5231,8934
                            ,4322,7922,6892,5224,4829,3829
                            ,6892,6872,4682,6723,8923,3492};
        //One int(4 bytes) hold 32 = 2^5 value,
        //About 4 * 125M Bytes
        //int sort[] = new int[1 << (32 - 5)];
        //Allocate small array for local test
        int sort[] = new int[1000];
        //Set all bit to 0
        for(int index = 0; index < sort.length; index++){
            sort[index] = 0;
        }
        for(int number : input){
            sort[number >>> 5] |= (1 << (number % 32));
        }
        int topNum = 0;
        outer:
        for(int index = sort.length - 1; index >= 0; index--){
            if(0 != sort[index]){
                for(int bit = 31; bit >= 0; bit--){
                    if(0 != (sort[index] & (1 << bit))){
                        System.out.println((index << 5) + bit);
                        topNum++;
                        if(topNum >= 3){
                            break outer;
                        }
                    }
                }
            }
        }
    }
}
    回复于
  • 1

    我做了我自己的代码，不确定它是什么“面试官”正在寻找

    private static final int MAX=100;
 PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
        queue.add(array[0]);
        for (int i=1;i<array.length;i++)
        {

            if(queue.peek()<array[i])
            {
                if(queue.size() >=MAX)
                {
                    queue.poll();
                }
                queue.add(array[i]);

            }

        }
    回复于
  • 0

    Possible improvements.

    如果文件包含10亿个数字，那么阅读它可能会很长...

    为了改善这种工作，您可以：

    • 将文件拆分为n个部分，创建n个线程，使n个线程分别查看文件中的100个最大数字（使用优先级队列），最后获得所有线程输出的100个最大数量 .

    • 使用群集执行此类任务，使用像hadoop这样的解决方案 . 在这里，您可以更加分割文件，并为10亿（或10 ^ 12）数字文件更快地输出 .

    回复于
  • 0

    此代码用于在 Unsorted array 中查找 N 个最大数字 .

    #include <iostream>


using namespace std;

#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000

void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);

int main() {


        int array[BILLION] // contains data

        int i=0, temp;

        int max[Array_Size];


        findLargest(max,array); 


        cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";

        for(i=0; i< Array_Size; i++)
            cout<< max[i] << endl;

        return 0;
    }




void findLargest(int max[], int array[])
{
    int i,temp,res;

    for(int k=0; k< Array_Size; k++)
    {
           i=0;

        while(i < BILLION)
        {
            for(int j=0; j< Array_Size ; j++)
            {
                temp = array[i];

                 res= checkDup(temp,max);

                if(res == 0 && max[j] < temp)
                    max[j] = temp;
            }

            i++;
        }
    }
}


int checkDup(int temp, int max[])
{
    for(int i=0; i<N_O_L_N_T_F; i++)
    {
        if(max[i] == temp)
            return -1;
    }

    return 0;
}

    这可能不是有效的，但可以完成工作 .

    希望这可以帮助

    回复于
  • 1

    我知道这可能会被埋没，但这是我对 radix MSD 的变化的想法 .

    pseudo-code:

    //billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];

for number in billion
    putInTop100Array(number)

function putInTop100Array(number){
    //basically if we got past all the digits successfully
    if(number == null)
        return true;
    msdIdx = getMsdIdx(number);
    msd = getMsd(number);
    //check if the idx above where we are is already full
    if(mynums[msdIdx][msd+1] > 99) {
        return false;
    } else if(putInTop100Array(removeMSD(number)){
        mynums[msdIdx][msd]++;
        //we've found 100 digits here, no need to keep looking below where we are
        if(mynums[msdIdx][msd] > 99){
           for(int i = 0; i < mds; i++){
              //making it 101 just so we can tell the difference
              //between numbers where we actually found 101, and 
              //where we just set it
              mynums[msdIdx][i] = 101;
           }
        }
        return true;
    }
    return false;
}

    函数 getMsdIdx(int num) 将返回最高有效数字的索引（非零） . 函数 getMsd(int num) 将返回最高有效数字 . 函数 removeMSD(int num) 将从数字中删除最重要的数字并返回该数字（如果删除最重要的数据后没有任何内容，则返回null数字） .

    完成此操作后，剩下的就是遍历 mynums 以获取前100位数字 . 这将是这样的：

    int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
    int timesAdded = 0;
    for(int j = 16; j >=0 && timesAdded < 100; j--){
        for(int k = mynums[i][j]; k > 0; k--){
            nums[idx] += j;
            timesAdded++;
            idx++;
        }
    }
}

    我应该注意，尽管上面看起来它具有很高的时间复杂度，但它实际上只会在 O(7*100) 左右 .

    快速解释这是怎么做的：本质上这个系统试图根据数字中数字的索引和数字的值来使用2d数组中的每个数字 . 它使用这些作为索引来跟踪在数组中插入了多少个值 . 当达到100时，它关闭所有“下部分支” .

    此算法的时间类似于 O(billion*log(16)*7)+O(100) . 我错了 . 此外，它很可能需要调试，因为它有点复杂，我只是把它写在我的头顶 .

    编辑：没有解释的Downvotes没有帮助 . 如果您认为这个答案不正确，请留下评论原因 . 很确定StackOverflow甚至会在你downvote时告诉你这样做 .

    回复于
  • -1

    管理单独的列表是额外的工作，每次找到另一个替换时，您必须在整个列表中移动 . 只需要输入它并进入前100名 .

    回复于

相关问题