数组中出现2次

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数组中出现2次，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1912字，纯文字阅读大概需要3分钟。

内容图文

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

分析：

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

[cpp] view plaincopyprint?

1. int fun1(const int a[])
2. {
3. int hash[1002]={0};
4. int x=0;
5. for(int i = 0; i<1001; i++)
6. {
7. if((++hash[a[i]]) == 2)
8. {
9. x = a[i];
10. break;
11. }
12. }
13. return x;
14. }

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

方法二、若不使用辅助的存储方式呢？已知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?

1. int fun2(const int a[])
2. {
3. int s1=0,s2;
4. s2 = 1001*1000/2;
5. for(int i = 0; i<1001; i++)
6. {
7. s1+=a[i];
8. }
9. return s1-s2;
10. }

内容总结

以上是互联网集市为您收集整理的数组中出现2次全部内容，希望文章能够帮你解决数组中出现2次所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端