相关疑难解决方法(0)

您将获得一个整数介于1和1,000,000之间的数组.一个整数在数组中两次.你怎么决定哪一个？你能想到一种方法来使用额外的内存来做到这一点.

ALGO:

• 解决方案1:
  1. 有一个哈希表
  2. 迭代数组并将其元素存储在哈希表中
  3. 一旦找到已经在哈希表中的元素,它就是dup元素
  优点:
  • 它在O(n)时间运行,只有1次通过
  缺点:
  • 它使用O(n)额外的内存
• 溶液2:
  1. 使用合并排序(O(nlogn)时间)对数组进行排序
  2. 再次解析,如果你看到一个元素两次,你得到了dup.
  优点:
  • 它不使用额外的内存
  缺点:
  • 运行时间大于O(n)

你们能想到更好的解决方案吗？

我们给出了一个大小为N的数组,其中包含0到N-2范围内的整数,包括0和N-2.

该阵列可以有多个重复的条目.我们需要在O(N)时间和常量空间中找到一个重复的条目.

我正在考虑获取阵列中所有entires的乘积和总和,以及0到N-2范围内所有数字的乘积和总和.

然后,总和的差异和产品的划分将给出两个方程式.如果给出只有两个重复的条目,这种方法会起作用,但由于可能有两个以上,我认为我的方法失败了.

有什么建议？

编辑:数组是不可变的.我意识到这是一个重要的信息,我很抱歉我忘了早些提到这一点.