找到一个单一的数量在一个列表[重复]

StackOverflow https://stackoverflow.com/questions/35185

  •  09-06-2019
  •  | 
  •  

题

这个问题已经有一个答案在这里：

什么是最好的算法找到一个数字，只发生一次在一个列表中的所有其他数字产生完全的两倍。

因此，在列表的整数(可以把它作为一个阵)各整数完全重复两次，只有一个除外。找到一，什么是最好的算法。

有帮助吗？

解决方案

最快的(O(n))和最高效率的存储器(O(1))的方式是与异或操作。

C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

这个打印"1"，这是唯一的一个发生一次。

这工作是因为你第一次打一些它标志着数字的变量，本身，和第二次取消标记已num与本身(更多或更少)。唯一的一个仍然没有标志的是您的非重复。

其他提示

通过这种方式，可以扩大这一想法很快找到 两个 独特的数字之间的一个列表中的重复。

让我们打电话的独特的号码a和b。首先采取的异或一切的，凯尔建议。我们得到的是一个^b。我们知道了^b!= 0时，由于一个!= b.任意选择1位^b，并将其用作掩--在更多的细节：选择x作为一个功率为2x(a^b)非零。

现在分列成两个子表--一个子列表中包含的所有数字y y&x==0，其余在其他子列表.顺便说一句，我们选择了x，我们知道，a和b是在不同的水桶。我们也知道，每一对重复的仍然是在同一桶。因此，我们现在可以适用ye olde"异或他们所有人"的伎俩为每桶独立，并发现什么a和b。

Bam。

O(N)时，O(N)存储器

HT=散列表

HT.明() 去名单中了 对于每一个项目，你看看

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

在结束时，该项目在HT是该项目。

注意(信用@Jared上堤):这个系统将找到的所有奇怪的情况的项目。

评论:我没有看到人们怎么能投票的解决方案，给你NLogN性能。在这宇宙的是，"更好的"?我更加感到震惊标所接受的答案s NLogN解决方案...

我不同意但是，如果记忆是需要是恒定不变，那么NLogN会(至今)最好的解决办法。

Kyle的解决办法显然赶不上情况的数据集不遵守规则。如果所有号码都在对算法将得到结果为零，完全相同的价值，如果零会是唯一的价值与单一的次数。

如果有多个个单一的次数值或三倍，结果将是errouness。

测试的数据集可能以及最终与一个更代价高昂的算法，无论是在存储器或时间。

Csmba的解决方案不会显示一些errouness数据(没有或一个以上的单一发生值)，而不是其他(quadrouples).关于他的解决办法，根据执行HT，无论是存和/或时间更然后O(n)。

如果我们不能肯定关于正确输入的设定、分类并且计数或使用hashtable计数出现与整数本身正在散的关键将是可行的。

我要说的是，使用排序的算法和随后经过排序的名单找到的数目是一个很好的方式来做到这一点。

现在的问题是找到"最好的"排序的算法。有很多的排序的算法，他们每个人都有其强有力和弱点，因此这是一个相当复杂的问题。的 维基百科的入口 似乎是一个很好的来源的信息。

执行红宝石：

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

需要指定什么你的意思是"最好"-一些，速度是所有的问题，并将合格的答案为"最好"-对于其他人，他们可能会原谅几十毫秒，如果解决方案是更加可读性。

"最好"是主观的，除非你有更加具体。

这说：

迭代的数字，每个数字的搜索名单数，当你到达的数量，返回只有1搜索结果的数量，你都做了。

似乎是最好的你可以做的是迭代过该列表，对每一个项目，将它添加到名单的"看见"项目或其他删除从"看到"如果已经有，并且在结束你的列表中的"看见"的项目将包括的单元。这是O(n)关于时间和n关于空间(在最坏的情况下，它会更好，如果该名单是排序).

事实上，他们在整数并不真正因素，因为没有什么特别的你可以做把它们加起来...是那里吗？

的问题

我不明白为什么选择回答是"最好的"通过的任何标准。O(N*铌酸镓镧)>O(N)，和它的更改的列表(或其他创造了它的一个副本，这仍然是更昂贵的空间和时间)。我失去了一些东西？

取决于如何大型/小型/多样化的数字虽然。基数的排序可能适用这将减少的排序的时间O(N记录N)方案通过一个大学学位。

排序方法而异的方法具有相同的时间的复杂性。XOR方法只是O(n)如果假定异或两个串是一个固定的时间操作。这等于说，整数列为界定。在这种情况下可以使用基数的排序进行排列在O(n)。

如果该数字没有界限的，那么异或需要时间O(k)在k长串位，并异或方法需要O(nk).现在再次数的排序将排列在时间O(nk).

你可以简单地把元素组成的散列直到你找到一个碰撞。在红宝石，这是一个衬垫。

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

所以， find_dupe([1,2,3,4,5,1]) 将返回1.

这实际上是一个共同的"欺骗"的采访问题。它通常是有关列表的一连续整数的一个重复。在这种情况下采访者往往是寻找您使用的高斯总和 n-整数，例如招 n*(n+1)/2 从中减去实际的总和。教科书的答案是这样的东西。 

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top