我最近在某个地方遇到过一个问题:
假设您有一个1001整数的数组.整数是随机顺序,但您知道每个整数在1到1000之间(包括1和1000).此外,每个数字在数组中只出现一次,但一个数字除外,它出现两次.假设您只能访问数组的每个元素一次.描述一个算法来查找重复的数字.如果您在算法中使用了辅助存储,是否可以找到不需要它的算法？
我感兴趣的是第二部分,即不使用辅助存储.你有什么主意吗？
我在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)空间中测试欺骗吗？
给定一个整数数组,其中一些数字重复1次,一些数字重复2次,只有一个数字重复3次,你如何找到重复3次的数字.不允许使用哈希.算法的复杂度应为O(n)
给定的阵列n+1整数,每个范围1来n,发现反复的整数.
在面试时我被问到这个问题.这是我的答案:鸽笼原则说必须重复一遍.我尝试使用二进制搜索方法,所以我在Matlab中做了这个,因为这就是我所知道的:
top = 0;
bot = 0;
for i=1:n+1
if P[i] > n/2
top = top+1;
else
bot = bot+1;
end
所以我认为其中一个,top或者bot,必须比n/2PhP 更大.取这个范围并重复.
我认为这是一个非常好的解决方案,但面试官有点暗示一个人可以做得更好.请发布您知道的更好的解决方案.
您将获得一个n + 2个元素的数组.数组的所有元素都在1到n的范围内.除了出现两次的两个数字外,所有元素都会出现一次.找到两个重复的数字.
例如,array = {4,2,4,5,2,3,1}和n = 5
伙计们我知道这个问题的4个可能的解决方案,但最近我遇到了一个我无法解释的解决方案.Below是解决方案的算法
traverse the list for i= 1st to n+2 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Example: A[] = {1,1,2,3,2}
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ;
so list now is {-1,1,2,3,2}
i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] …对于初学者,我确实看过这些问题:
给定一个整数数组,其中一些数字重复1次,一些数字重复2次,只有一个数字重复3次,你怎么找到重复3次的数字
这一个不同:
给出一个带有一个唯一编号的未排序整数数组,其余数字重复3次,即:
{4,5,3, 5,3,4, 1, 4,3,5 }
我们需要在O(n)时间和O(1)空间中找到这个唯一的数字
注意:这不是一个功课,只是我遇到一个很好的问题
问题:给出一系列从1到n-1的数字,其中一个数字只重复一次.(例如:1 2 3 3 4 5).你怎么能找到重复的数字？
通常,对这个问题的所谓"聪明"回答是将其总结并找出与预期总和的差异.但为什么不只是走过清单并检查之前的数字呢？两者都是O(n).我错过了什么吗？