输入:给定n个元素的数组,其中包含从0到n-1的元素,这些数字中的任何一个都会出现任意次数.
目标:在O(n)中找到这些重复数字并仅使用常量存储空间.
例如,设n为7,数组为{1,2,3,1,3,0,6},答案应为1和3.我在这里检查了类似的问题,但答案使用了一些数据结构等HashSet.
任何有效的算法都相同？
确定1到N范围内缺失值的常见访谈问题已经完成了一千多次.变化包括2个缺失值,最多K个缺失值.
示例问题:范围[1,10](1 2 4 5 7 8 9 10)= {3,6}
以下是各种解决方案的示例:
简单的面试问题变得更难:给出数字1..100,找到丢失的数字
我的问题是,看到一个缺失值的简单情况是O(n)复杂性,并且较大情况的复杂性收敛于大于O(nlogn)的大小:
通过对范围进行排序(mergesort)并迭代它来观察缺失的元素,难道只是更容易回答这个问题吗？
该解决方案应该不超过O(nlogn),并且能够解决1到N之外的范围的问题,例如10到1000或-100到+100等......
是否有理由相信上述SO链接中的给定解决方案将比基于排序的解决方案更好地存在大量缺失值？
注意:对于这个问题,似乎有很多常见的解决方案,假设只有一个数论的方法.如果在S/E采访中被问到这样一个问题,使用更多的计算机科学/算法方法是不谨慎的,假设该方法与数论解决方案的复杂性相同......
更多相关链接:
你得到一个N 64位整数数组.N可能非常大.你知道每个整数1..N在数组中出现一次,除了缺少一个整数和一个重复的整数.
编写线性时间算法以查找丢失和重复的数字.此外,您的算法应该在小的恒定空间中运行并保持数组不变.
资料来源:http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/
我得到了一个n个整数的列表,这些整数在1到n的范围内.列表中没有重复项.但是列表中缺少其中一个整数.我必须找到缺少的整数.
Example: If n=8
I/P [7,2,6,5,3,1,8]
O/P 4
I am using a simple concept to find the missing number which is to get the
sum of numbers
total = n*(n+1)/2
And then Subtract all the numbers from sum.
但是如果数字的总和超出允许的最大整数,则上述方法将失败.
所以我搜索了第二个解决方案,我找到了一个方法如下:
1) XOR all the elements present in arr[], let the result of XOR be R1.
2) XOR all numbers from 1 to n, let XOR be R2.
3) XOR of R1 and R2 gives the missing number.
这个方法是如何工作的？在上述情况下,R1和R2的XOR如何找到缺失的整数？
我在一个采访网站上遇到了这个问题.该问题要求在单个阵列中有效地实现三个堆栈,使得在整个阵列空间中没有剩余空间之前没有堆栈溢出.
为了在数组中实现2个堆栈,非常明显:第一个堆栈从LEFT变为RIGHT,第二个堆栈从RIGHT增长到LEFT; 当stackTopIndex交叉时,它会发出溢出信号.
提前感谢您的深刻回答.
如何从排序列表中找到pythonic方式中缺少的数字
a=[1,2,3,4,5,7,8,9,10]
我遇到过这篇文章,但有更简单有效的方法吗？
假设我有一个清单
ArrayList<String> arr = new ArrayList(Arrays.asList("N1", "N2", "N3", "N5"));
我怎么找到"N4",我的意思是,我怎么发现丢失的整数是4？
到目前为止我尝试过的
Integer missingID = arr.stream().map(p -> Integer.parseInt(p.substring(1))).sorted()
.reduce((p1, p2) -> (p2 - p1) > 1 ? p1 + 1 : 0).get();
这不起作用,因为reduce在这种情况下不打算以我需要的方式工作,实际上,我不知道怎么做.如果没有丢失的数字,则必须是下一个"N6" - or just 6 -(在此示例中)
它必须使用java标准流的库,不使用第三方.
假设你有一个大小为n的数组A [1..n],它包含集合{1..n}中的元素.但是,缺少两个元素(并且可能重复了两个数组元素).找到缺少的元素.
例如,如果n = 5,A可以是A [5] = {1,2,1,3,2}; 所以缺少的元素是{4,5}
我使用的方法是:
int flag[n] = {0};
int i;
for(i = 0; i < n; i++) {
flag[A[i]-1] = 1;
}
for(i = 0; i < n; i++) {
if(!flag[i]) {
printf("missing: %d", (i+1));
}
空间复杂性来自O(n).我觉得这是一个非常儿童和低效的代码.那么请你提供一个更好的空间和时间复杂度的更好的算法.
这个问题的存在只是因为纯粹的好奇心.不是作业.
找到在数组1..n中找到两个缺失数字的最快方法
所以,在一篇相关的文章中:在一组数字中找到缺失数字的最快方法 我发现你可以通过总结和减去总数来快速完成.
但是2个数字怎么样？
所以,我们的选择是:
还要别的吗？可能有O(n)解决方案吗？我在其中一个网站的ruby部分找到了这个,但是考虑了任何语言(除非语言有一些特定的东西)
有一台机器有O(1)内存.我们想要第一次传递n个数字(逐个),我们再次排除两个数字,我们将n-2传递给机器.写一个找到缺失数字的算法.这是一个面试问题,我无法解决.