首页 数据库 mysql教程 数组中出现2次

数组中出现2次

Jun 07, 2016 pm 03:09 PM
出现 数组 整数 组成

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

假设你有一个用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
  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

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

<p>
</p><p>
</p><p><strong>[cpp]</strong> 
view plaincopyprint?</p>

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



登录后复制
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

如何使用 foreach 循环去除 PHP 数组中的重复元素? 如何使用 foreach 循环去除 PHP 数组中的重复元素? Apr 27, 2024 am 11:33 AM

使用foreach循环去除PHP数组中重复元素的方法如下:遍历数组,若元素已存在且当前位置不是第一个出现的位置,则删除它。举例而言,若数据库查询结果存在重复记录,可使用此方法去除,得到不含重复记录的结果。

PHP 数组键值翻转:不同方法的性能对比分析 PHP 数组键值翻转:不同方法的性能对比分析 May 03, 2024 pm 09:03 PM

PHP数组键值翻转方法性能对比表明:array_flip()函数在大型数组(超过100万个元素)下比for循环性能更优,耗时更短。手动翻转键值的for循环方法耗时相对较长。

PHP数组多维排序实战:从简单到复杂场景 PHP数组多维排序实战:从简单到复杂场景 Apr 29, 2024 pm 09:12 PM

多维数组排序可分为单列排序和嵌套排序。单列排序可使用array_multisort()函数按列排序;嵌套排序需要递归函数遍历数组并排序。实战案例包括按产品名称排序和按销售量和价格复合排序。

PHP数组深度复制的艺术:使用不同方法实现完美复制 PHP数组深度复制的艺术:使用不同方法实现完美复制 May 01, 2024 pm 12:30 PM

PHP中深度复制数组的方法包括:使用json_decode和json_encode进行JSON编码和解码。使用array_map和clone进行深度复制键和值的副本。使用serialize和unserialize进行序列化和反序列化。

深度复制PHP数组的最佳实践:探索高效的方法 深度复制PHP数组的最佳实践:探索高效的方法 Apr 30, 2024 pm 03:42 PM

在PHP中执行数组深度复制的最佳实践是:使用json_decode(json_encode($arr))将数组转换为JSON字符串,然后再将其转换回数组。使用unserialize(serialize($arr))将数组序列化为字符串,然后将其反序列化为新数组。使用RecursiveIteratorIterator迭代器对多维数组进行递归遍历。

PHP 数组分组函数在数据整理中的应用 PHP 数组分组函数在数据整理中的应用 May 04, 2024 pm 01:03 PM

PHP的array_group_by函数可根据键或闭包函数对数组中的元素分组,返回一个关联数组,其中键是组名,值是属于该组的元素数组。

PHP 数组分组函数在查找重复元素中的作用 PHP 数组分组函数在查找重复元素中的作用 May 05, 2024 am 09:21 AM

PHP的array_group()函数可用于按指定键对数组进行分组,以查找重复元素。该函数通过以下步骤工作:使用key_callback指定分组键。可选地使用value_callback确定分组值。对分组元素进行计数并识别重复项。因此,array_group()函数对于查找和处理重复元素非常有用。

PHP 数组合并去重算法:并行的解决方案 PHP 数组合并去重算法:并行的解决方案 Apr 18, 2024 pm 02:30 PM

PHP数组合并去重算法提供了并行的解决方案,将原始数组分成小块并行处理,主进程合并块的结果去重。算法步骤:分割原始数组为均等分配的小块。并行处理每个块去重。合并块结果并再次去重。

See all articles