我最近参加了一次采访,我被问到"编写一个程序,从10亿个数字中找出100个最大的数字."
我只能给出一个强力解决方案,即以O(nlogn)时间复杂度对数组进行排序并获取最后100个数字.
Arrays.sort(array);
面试官正在寻找更好的时间复杂性,我尝试了其他一些解决方案但未能回答他.有更好的时间复杂度解决方案吗？
3-d中的点由(x,y,z)定义.任何两个点(X,Y,Z)和(x,y,z)之间的距离d是d = Sqrt [(Xx)^ 2 +(Yy)^ 2 +(Zz)^ 2].现在文件中有一百万个条目,每个条目都是空间中的某个点,没有特定的顺序.给定任意点(a,b,c)找到最近的10个点.您将如何存储百万点以及如何从该数据结构中检索这10个点.
我经常发现自己遇到这个问题:给定一个序列,找到k-最小的元素.问题并不那么难,但我正在寻找的是一种"习惯性"的方式来做到这一点既安全又很少错误)并且沟通意图很好.所以最终做的是对序列进行排序,然后取第一个k元素:
std::sort(container.begin(),container.end());
std::vector<T> k_smallest(container.begin(),container.begin() + k);
在我看来这既安全又易于理解,但这里的复杂性是nlogn + k,而不仅仅是n.你们是如何做到这一点的,是否有一种自觉的方式(使用一些模糊的功能)可以提供最佳的复杂性而无需重新实现轮子
可能重复:
从一亿个数字中检索前100个数字
我有一个数组,其中包含0到9之间的正数,(数字可以重复).我想找到N个最大元素的总和
For example array = 5 1 2 4 and N=2
ans = 5+4 = 9
简单方法:排序数组并找到n个最大元素的总和.但我不想用它