数组中出现2次

假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你 只能对这个数组做一次处理 ，用一种算法找出重复的那个数字。 如果你在运算中使

假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你 只能对这个数组做一次处理 ，用一种算法找出重复的那个数字。 如果你在运算中使用了 辅助的存储方式 ，那么你能找到不用这种方式的算法吗?

分析 ：

方法一 、 若 使用辅助的存储方式 ， 该选择何种存储方式呢 ？ 可使用hash的存储方式，以1到1000作为hash表的索引，遍历原数组，统计各数字出现的个数并存储到以该数字为索引值的hash表中，若某个hash[x]的值为2则退出循环，x就是重复出现两次的数字。时间复杂度最坏是O(n)。 优点：高效率，缺点：消耗的内存空间过大。 代码如下：

[cpp] view plaincopyprint?

int fun1( const int a[]) { int hash[1002]={0}; int x=0; for ( int i = 0; i { if ((++hash[a[i]]) == 2) { x = a[i]; break ; } } return x; }

int fun1(const int a[])
{
  int hash[1002]={0};
  int x=0;
  for(int i = 0; i 

方法二 、 若不使用辅助的存储方式呢 ？ 已 知 1001个整数组成的数组只有一个数字出现了两次，且整数都在1到1000之间， 所以可推得数组里面包含了1到1000之间的所有数字为[1,2,3……1000]和一个出现两次的x为1到1000中的任一个数字。这样就可以计算原数组里的所有数字之和S1和等差数列[1,2,3……1000] 的和 S2，再计算S1与S2之差，该差就是原数组中出现两次的数字x。时间复杂度是固定的O(n)。 优缺点：内存空间消耗几乎没有，但是效率要输于使用hash表的存储方式。 代码如下：

[cpp] view plaincopyprint?

int fun2( const int a[]) { int s1=0,s2; s2 = 1001*1000/2; for ( int i = 0; i { s1+=a[i]; } return s1-s2; }

查看更多关于数组中出现2次的详细内容...