我有一段时间有一个有趣的面试经历.问题开始很简单:
Q1:我们有包含数字的袋子
1,2,3,...,100.每个数字只出现一次,因此有100个数字.现在从包里随机挑出一个号码.找到丢失的号码.
当然,我之前听过这个采访问题,所以我很快回答了以下问题:
A1:嗯,这些数字的总和
1 + 2 + 3 + … + N是(N+1)(N/2)(见维基百科:算术系列之和).因为N = 100,总和是5050.因此,如果包中存在所有数字,则总和将是精确的
5050.由于缺少一个数字,总和将小于此数值,差异就是该数字.所以我们可以在O(N)时间和O(1)空间中找到丢失的数字.
在这一点上,我认为我做得很好,但突然之间,这个问题发生了意想不到的变化:
Q2:这是正确的,但是现在如果缺少两个数字你会怎么做？
我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题.面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一遍获得一些信息后再做第二遍,但我真的只是拍摄在黑暗中而不是实际上有一条清晰的解决方案.
面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法.在这一点上,我有点不高兴(因为事先不知道答案),并询问这是一般的(阅读:"有用")编程技术,还是只是一个技巧/问题答案.
面试官的回答让我感到惊讶:你可以概括一下找到3个缺失数字的技巧.实际上,您可以将其概括为找到k个缺失的数字.
Qk:如果行李中缺少k个号码,您会如何有效地找到它？
这是几个月前,我仍然无法弄清楚这种技术是什么.显然有一个?(N)时间下限,因为我们必须扫描所有数字至少一次,但是访问者坚持解决技术的时间和空间复杂度(减去O(N)输入扫描的时间)在k而不是N中定义.
所以这里的问题很简单:
存在大小为n的数组,并且数组中包含的元素在1和n-1之间,使得每个元素出现一次并且仅一个元素出现多次.我们需要找到这个元素.
虽然这是一个非常常见的问题,但我仍然没有找到合适的答案.大多数建议是我应该将数组中的所有元素相加,然后从中减去所有索引的总和,但如果元素的数量非常大,这将不起作用.它会溢出.关于XOR门的使用也有一些建议dup = dup ^ arr[i] ^ i,我不清楚.
我已经提出了这个算法,这是一个增加算法的增强,并将在很大程度上减少溢出的机会!
for i=0 to n-1
begin :
diff = A[i] - i;
sum = sum + diff;
end
diff包含重复元素,但使用此方法我无法找到重复元素的索引.为此,我需要再次遍历数组,这是不可取的.任何人都可以提出一个更好的解决方案,不涉及添加方法或XOR方法在O(n)中工作？
(这是一个概括:在O(n)时间和O(1)空间中查找重复项)
问题:分别编写具有O(n)和O(1)的时间和空间复杂度的C++或C函数,它们在给定数组中找到重复整数而不改变它.
示例:给定{1,0,-2,4,4,1,3,1,-2}函数必须打印1,-2和4一次(按任意顺序).
(INT_MAX – INT_MIN)/4 + 1.
#include <stdio.h>
void set_min_max(int a[], long long unsigned size,\
int* min_addr, int* max_addr)
{
long long unsigned i;
if(!size) return;
*min_addr = *max_addr = a[0];
for(i = 1; i < size; ++i)
{
if(a[i] < *min_addr) *min_addr = a[i];
if(a[i] > *max_addr) *max_addr = a[i];
}
}
void print_repeats(int a[], long long unsigned size)
{
long long unsigned i;
int min, max = min;
long long diff, q, …假设你有一个大小为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).我觉得这是一个非常儿童和低效的代码.那么请你提供一个更好的空间和时间复杂度的更好的算法.
我得到了这个问题的考试:
给定整数数组,使用O(N)时间复杂度和O(1)空间复杂度找到第一个不在数组中重复的数字.
我想不出任何解决方案.我知道我可以迭代数组并维护一个linkedhashmap,它将存储数组元素和它出现的次数,然后最后我必须搜索hashmap来找到那个数字.空间复杂度大于O(1)但我想不出其他解决方案.
我也仔细阅读问题,并说数组的最大尺寸为100万.我认为如果我们可以创建一个自定义散列图,它将使用100万大小的固定大小的数组,那么这可以在O(1)空间复杂度中实现,因为在这种情况下,所需的存储将是恒定的,但如果我是正确的则不确定.如果有任何其他解决方案,请告诉我.
给定N个整数的数组,使得只重复一个整数.在O(n)时间和常量空间中找到重复的整数.整数值或N的值没有范围
例如,给出一个由6个整数组成的数组,如23 45 67 87 23 47.答案是23(我希望这涵盖模糊和含糊的部分)
我在网上搜索但无法找到任何这样的问题,其中整数范围没有固定.还这里是,回答一个类似的问题,以矿一个例子,但在这里,他创建的哈希表C++中的最高整数值,但CPP不允许这样的64位的计算机上创建与2 ^ 64元件(阵列).
对不起,在数组不可变之前我没有提到它
检测数组中重复项的两种常用方法:
1)排序第一,时间复杂度O(n log n),空间复杂度O(1)
2)哈希集,时间复杂度O(n),空间复杂度O(n)
是否有第三种检测重复的方法？
请不要回答蛮力.
假设有一个元素数组没有重复,除了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)空间中查找重复项
我需要编写一个对大小为[0..N-1]的数组进行排序的算法,该算法填充了范围[0..N-1]的值.数组中的值不能重复.排序应该在线性时间内工作,我只允许使用一些额外的变量.
请写我写的代码.据我猜,最糟糕的时间是2*N. 还是一个线性时间吗？是否有可能使速度更快？
public int sort(){
int i = 0;
while (i < n){
if (a[i] != i)
switchElements(a[i], a[a[i]]);
else
i++;
}
return count;
}
额外的1 我真的需要对数组进行排序,因为排序只是任务的一部分.完整的任务是找到数组中的重复值,线性时间,没有其他变量.