<h2>1、数组中重复的数字</h2>
<h2>题目描述</h2>
<p>在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。</p>
<pre class="blockcode">
<code class="language-html">Input:
{2, 3, 1, 0, 2, 5}
Output:
2</code></pre>
<h2>解题思路</h2>
<p>1）任意一个重复的数字，所以当查找到第一个重复的时候就可以return</p>
<p>2)如果要求时间复杂度O(N)，空间复杂度O(1)。则不能使用排序算法。如果没有要求，可以先进行排序，扫描排序之后的数组即可。</p>
<p>3）解决思路一：采用将值为i的元素调整到第i个位置，如果发现位置上面的元素已经有对应数值了，则发现有重复。先进行交换，将所有数字放入对应的位置，交换前面加上一个判断，如果你发现对应位置的数字是对的，然后你又发现一个这样的数字，那这个数字就是重复的一个数字。如果发现多个，那将重复的数字放在数组中进行保存。</p>
<p> 解决思路二：哈希表。从头到尾扫描数组，每扫描到一个数字，判断该数字是否在哈希表中，如果该哈希表还没有这个数字，那么加入哈希表，如果已经存在，则返回该数字；时间复杂度：O(n)，空间复杂度:O(n)</p>
<p> 解决思路三：排序，再遍历</p>
<p>交换数字，按位置比较。</p>
<blockquote>
<ol><li>public class repeatNum3 {</li>
<li> /**</li>
<li> * @param ycy</li>
<li> */</li>
<li> public static void main(String[] args) {</li>
<li> // TODO Auto-generated method stub</li>
<li> int[] num= {2,3,1,0,2,5};</li>
<li> int repeat = 0;</li>
<li> int j = 0;</li>
<li> </li>
<li> if(num == null || num.length<=0){</li>
<li> System.out.println("不存在重复的数据");</li>
<li> }</li>
<li> System.out.println("数据长度"+num.length);</li>
<li> for(int i=0;i<num.length;i++){</li>
<li> while(num[i] != i){</li>
<li> if(num[i] == num[num[i]]){</li>
<li> repeat = num[i];</li>
<li> System.out.println("存在重复的数据"+repeat);</li>
<li> return;</li>
<li> }</li>
<li> swap(num,i,num[i]);</li>
<li> }</li>
<li> }</li>
<li> return;</li>
<li> }</li>
<li> public static void swap(int[] num,int i,int j){</li>
<li> int t = num[i];</li>
<li> num[i] = num[j];</li>
<li> num[j] = t;</li>
<li> }</li>
<li>}</li>
</ol></blockquote>
<p><img alt="" class="blockcode" height="738" src="https://201907.oss-cn-shanghai.aliyuncs.com/cs/5606289-e4f8be2d1e24f3272e5505cbd164d1d4.png" width="776"></p>
<h3>各种排序算法比较</h3>
<table border="0" cellpadding="0" cellspacing="0"><tbody><tr><td colspan="9">
<p>各种常用排序算法</p>
</td>
</tr><tr><td rowspan="2">
<p>类别</p>
</td>
<td rowspan="2">
<p>排序方法</p>
</td>
<td colspan="3">
<p>时间复杂度</p>
</td>
<td>
<p>空间复杂度</p>
</td>
<td>
<p>稳定性</p>
</td>
<td>
<p>复杂性</p>
</td>
<td>
<p>特点</p>
</td>
</tr><tr><td>
<p>最好</p>
</td>
<td>
<p>平均</p>
</td>
<td>
<p>最坏</p>
</td>
<td>
<p>辅助存储</p>
</td>
<td>
<p></p>
</td>
<td>
<p>简单</p>
</td>
<td>
<p></p>
</td>
</tr><tr><td rowspan="2">
<p>插入</p>
<p>排序</p>
</td>
<td>
<p>直接插入</p>
</td>
<td>
<p>O(N)</p>
</td>
<td>
<p>O(N2)</p>
</td>
<td>
<p>O(N2)</p>
</td>
<td>
<p>O(1)</p>
</td>
<td>
<p>稳定</p>
</td>
<td>
<p>简单</p>
</td>
<td>
<p></p>
</td>
</tr><tr><td>
<p>希尔排序</p>
</td>
<td>
<p>O(N)</p>
</td>
<td>
<p>O(N1.3)</p>
</td>
<td>
<p>O(N2)</p>
</td>
<td>
<p>O(1)</p>
</td>
<td>
<p>不稳定</p>
</td>
<td>
<p>复杂</p>
</td>
<td>
<p></p>
</td>
</tr><tr><td rowspan="2">
<p>选择</p>
<p>排序</p>
</td>
<td>
<p>直接选择</p>
</td>
<td>
<p>O(N)</p>
</td>
<td>
<p>O(N2)</p>
</td>
<td>
<p>O(N2)</p>
</td>
<td>
<p>O(1)</p>
</td>
<td>
<p>不稳定</p>
</td>
<td>
<p></p>
</td>
<td>
<p></p>
</td>
</tr><tr><td>
<p>堆排序</p>
</td>
<td>
<p>O(N*log2N)</p>
</td>
<td>
<p>O(N*log2N)</p>
</td>
<td>
<p>O(N*log2N)</p>
</td>
<td>
<p>O(1)</p>
</td>
<td>
<p>不稳定</p>
</td>
<td>
<p>复杂</p>
</td>
<td>
<p></p>
</td>
</tr><tr><td rowspan="2">
<p>交换</p>
<p>排序</p>
</td>
<td>
<p>冒泡排序</p>
</td>
<td>
<p>O(N)</p>
</td>
<t |
|
转播
