剑指offer-50、数组中重复的数字
<h2 id="题目描述">题目描述</h2><p>在⼀个⻓度为 n 的数组⾥的所有数字都在 0 到n-1 的范围内。 数组中某些数字是重复的，但不知<br>
道有⼏个数字是重复的。也不知道每个数字重复⼏次。请找出数组中第⼀个重复的数字。 例如，如果输⼊⻓度为 7 的数组 ，那么对应的输出是第⼀个重复的数字 2 。没有重复的数字<br>
返回 -1 。</p>
<p>示例1</p>
<p>输⼊<br>
[ 2, 3, 1, 0, 2, 5, 3 ]</p>
<p>返回值<br>
2</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="借用set">借用Set</h3>
<p>⾸先可能想到的做法，就是借助 set ，如果元素不存在 set 中，就将元素添加进去，如果 set<br>
中包含该元素，就返回该元素即可。如果⼀直都没有重复的，那么最后返回 -1 。</p>
<pre><code class="language-java">public class Solution {
public int duplicate(int[] numbers) {
if (numbers != null) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
if (set.contains(numbers)) {
return numbers;
} else {
set.add(numbers);
}
}
}
return -1;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n) ，最差的情况可能遍历完所有的元素</li>
<li>空间复杂度： O(n) ，最⼤需 要set ⼤⼩为 n</li>
</ul>
<h3 id="借助数组">借助数组</h3>
<p>可以直接借助数组，因为所有数字都在 0 到 n-1 的范围内，⽤⼀个⼤⼩为 n 的数组，就可以对所有的数字进⾏统计个数，如果个数超过 1 ，那么肯定是重复的数字，如果没有重复的数字，则返回 -1 ；</p>
<pre><code class="language-java">public class Solution {
public int duplicate(int[] numbers) {
if (numbers != null) {
int[] nums = new int;
for (int i = 0; i < numbers.length; i++) {
if (nums] == 1) {
return numbers;
} else {
nums] = 1;
}
}
}
return -1;
}
}
</code></pre>
<p>同样这种做法的时间复杂度和空间复杂度都是 O(n) ,并没有优化太多。</p>
<p>那么有没有空间复杂度为O(1) 的做法呢？</p>
<h3 id="操作原数组最优">操作原数组（最优）</h3>
<p>不借助额外的空间，那么就只能操作原数组了。如果没有重复的情况，那么这些数字排序后，数字i 和数组下标i 应该是⼀⼀对应的。不会出现多个数字i 的情况。</p>
<p>基于这个原则，在遍历数组的时候，将元素 i 调整到下标 i 的位置，如果下标i的位置已经有元<br>
素，那么说明冲突了，这个元素肯定是重复的，否则继续调整后⾯的。如果没有发现重复的数字，就返回 -1 。</p>
<pre><code class="language-java">public class Solution {
public int duplicate(int[] numbers) {
int i = 0;
while(i < numbers.length) {
if(numbers == i) {
i++;
continue;
}
if(numbers] == numbers) return numbers;
int tmp = numbers;
numbers = numbers;
numbers = tmp;
}
return -1;
}
}
</code></pre>
<p>但是上⾯的做法，不适合求解多个重复数字的例⼦，因为调换的时候，很容易将后⾯的数字换到前⾯去，就会导致求解出来不是第⼀个重复的数字（可以⽤来求解任意的重复数字），可能是第2，3... 或者其他的重复数字。譬如： 正确的解应该是 2 ，但是由于第⼀次把 6 和最后<br>
的0 调换了位置，就会导致求解出来的值为 0 。</p>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19346905
頁:
[1]