埃森哲面试问题:
您已经获得了一个大小数组,2n+1其中包含n一对整数(可以是+ve,-ve或0)和一个不成对的元素.
你怎么会找到不成对的元素？
对意味着重复.所以(3,3)是一对和(3,-3)是不是一对.
我在Reddit上看到了这个问题,并没有提出积极的解决方案,我认为这是一个完美的问题.这是关于面试问题的一个主题:
编写一个采用大小为m的int数组的方法,如果数组由数字n ... n + m-1组成,则返回(True/False),该范围内的所有数字以及该范围内的数字.不保证数组已排序.(例如,{2,3,4}将返回true.{1,3,1}将返回false,{1,2,4}将返回false.
我遇到的问题是我的采访者一直要求我优化(更快的O(n),更少的内存等),他声称你可以在数组的一次传递中使用恒定量的记忆.从未想过那一个.
除了您的解决方案,请指出他们是否认为该阵列包含唯一的项目.同时指出您的解决方案是否假设序列从1开始.(我稍微修改了一下这个问题以允许它变为2,3,4 ......)
编辑:我现在认为在空间算法中不存在处理重复的线性时间和常数.任何人都可以验证吗？
重复问题归结为测试以查看数组是否在O(n)时间,O(1)空间中包含重复项.如果可以这样做,您可以先测试,如果没有重复,则运行算法.那么你可以在O(n)时间O(1)空间中测试欺骗吗？
找到在列表中只出现一次的数字的最佳算法是什么,其中所有其他数字恰好发生两次.
因此,在整数列表中(让它作为一个数组),每个整数重复两次,除了一个.找到那个,什么是最好的算法.
有一个大小为n的数组(数字介于0和n - 3之间),只重复2个数字.元素随机放置在数组中.
例如,在{2,3,6,1,5,4,0,3,5} n = 9,重复数为3和5.
找到重复数字的最佳方法是什么？
PS [你不应该使用排序]
给定一个n个整数元素的数组,如何在不使用任何额外空间的情况下在O(n)时间内找到数组中是否存在重复项.
额外的空间意味着额外的O(n)空间.
Xor操作员是否以任何方式提供帮助.
我能想到的是:
ALGO:
你能想到比这更好的解决方案吗？使用O(n)运行时并且不使用额外的空间
今天,一位采访者问我这个问题.我的直接反应是我们可以简单地进行线性搜索,将当前元素与数组中的前一个元素进行比较.然后他问我如何在不到线性的时间内解决问题.
假设
[0, n],其中n是数组的长度.示例数组:[0,1,2,3,4,5,6,7,8,8,9]
我试图想出一个分而治之的算法来解决这个问题,但我并不相信这是正确的答案.有没有人有任何想法？
我有一个算法问题,我在工作中遇到但未能提出一个令人满意的解决方案.我浏览了这个论坛一些,最接近我遇到同样的问题是如何在一个混洗的连续整数数组中找到一个重复的元素？.
我有一个N个整数元素的列表,它可以包含元素1-M(M> N),进一步列表是未排序的.我想要一个将此列表作为输入的函数,并返回列表中不存在的1-M范围内的值.该列表不包含重复项.我希望有一个o(N)解决方案,没有使用额外的空间UPDATE:函数无法更改原始列表L.
例如N = 5 M = 10列表(L):1,2,4,8,3然后f(L)= 5说实话我不在乎它是否返回5以外的元素,只要它满足以上的约束
到目前为止,我提出的唯一解决方案是使用额外的M元素数组.遍历输入列表并将相应的数组元素设置为1(如果列表中存在).然后再次遍历此列表并返回值为0的第一个元素的索引.如您所见,这会使用额外的o(M)空间并具有复杂度2*o(N).任何帮助我们都会感激.
感谢大家的帮助.堆栈溢出社区绝对是非常有用的.为每个人提供一些我正在努力解决的问题的背景.我有一组M令牌,我给一些客户(每个客户一个).当客户完成令牌后,他们就会回到我的堆里.正如您所看到的那样,我给客户端一个令牌进行排序.
所以M = 3令牌
client1:1 <2,3>
client2:2 <3>
client1返回:1 <1,3>
客户端3:3 <1>
现在问题是给client4令牌1.我可以在这个阶段给出客户端4令牌2并对列表进行排序.不确定这是否有帮助.在任何情况下,如果我想出一个很好的清洁解决方案,我一定会发布它
只是意识到我可能会困扰每个人.我被叫时,我没有免费令牌列表.我可以静态地维护这样的列表,但我宁愿不这样做
我遇到了一篇文章如何在一个混洗的连续整数数组中找到一个重复的元素？但后来意识到这很多输入都失败了.
例如:
arr[] = {601,602,603,604,605,605,606,607}
#include <stdio.h>
int main()
{
int arr[] = {2,3,4,5,5,7};
int i, dupe = 0;
for (i = 0; i < 6; i++) {
dupe = dupe ^ a[i] ^ i;
}
printf ("%d\n", dupe);
return 0;
}
如何修改此代码,以便可以找到所有案例的重复元素？
我想计算域内偶数的总和.我有两个解决方案,但我不确定每个解决方案的优点/缺点.哪种解决方案最佳？
import sys
domain = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Cal1 = sum(filter(lambda n : n % 2 == 0, domain))
Cal2 = sum([n for n in domain if n % 2 == 0])
sys.stdout.write("Cal1 = {0}\n".format(Cal1))
sys.stdout.write("Cal2 = {0}\n".format(Cal2))
假设有一个元素数组没有重复,除了1个数字,
ex. 1,2,13,4,7,11,2,6
如何以有效的方式找到重复的数字？我们可以在O(n)时间使用哈希表(HT)并使用如下的O(n)空间.
if(HT.Contains(item)) -> this is the duplicate
else
ht.add(item)
在空间和时间复杂性方面有更好的方法吗？
注意: 这个问题不是以下两个不同的问题的重复.
如果整数是连续的,则可以使用此链接中的解决方案如何在一个混乱的连续整数数组中找到一个复制元素
如果n个元素的数组包含从0到n-1的元素,则只有此链接具有解决方案在O(n)时间和O(1)空间中查找重复项
这个问题非常类似于如何在一个混洗连续整数数组中找到重复元素？,但有一些额外的要求.
您有一个连续整数列表,没有特定的顺序.无法保证这些整数的范围或列表中的元素数量.
此列表缺少一个整数,并包含另一个整数的副本.
这样一个列表的一个例子是{16,12,13,17,14,13}; 在这种情况下,缺少的整数是15,重复的是13.
考虑到小数据集和大数据集,找到这两个数字的最省时的方法是什么？有没有比O(n log n)更好的时间复杂度的解决方案,它不会阻塞小数据集？
有一个10,000的数组.它以随机顺序存储数字1到10,000.
每个号码只出现一次.
现在,如果从该数组中删除任何数字,并将任何其他数字复制到数组中.
我们如何确定哪个数字是重复的,最小的复杂性？
注意:我们不能使用另一个阵列.