相关疑难解决方法(0)

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

ALGO:

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

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

在数组[10]中,数组中有1到9的数字,其中一个数字重复(重复数也在1到9之间)如何在不使用循环的情况下找到重复的数字,并且数组可以被横向移动只有一次从上到下.

这不是作业,这是在采访中被问到的