Github倉庫位址：https://github.com/Damaer/CodeSolution
刷題筆記位址：https://damaer.github.io/CodeSolution/
倉庫介紹：刷題倉庫：CodeSolution
題目描述
在一個長度為n的數組裡的所有數字都在
到
n-1
的範圍内。數組中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中第一個重複的數字。例如，如果輸入長度為
7
的數組
[2,3,1,0,2,5,3]
，那麼對應的輸出是第一個重複的數字
2
。沒有重複的數字傳回-1。
示例1
輸入
[2,3,1,0,2,5,3]
傳回值
2
思路以及解答
我們首先可能想到的做法，就是借助
set
，如果元素不存在
set
中，就将元素添加進去，如果
set
中包含該元素，就傳回該元素即可。如果一直都沒有重複的，那麼最後傳回-1。
代碼如下：
import java.util.*;
public class Solution {
public int duplicate(int[] numbers) {
// write code here
if(numbers!=null) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
if (set.contains(numbers[i])) {
return numbers[i];
} else {
set.add(numbers[i]);
}
}
}
return -1;
}
}
複制
時間複雜度為
O(n)
，因為最差的情況可能周遊完所有的元素；空間複雜度也是
O(n)
，最大需要
set
大小為
n
。
當然除了set，我們也可以直接借助數組，因為所有數字都在
到
n-1
的範圍内，我們用一個大小為n的數組，就可以對所有的數字進行統計個數，如果個數超過1，那麼肯定是重複的數字，如果沒有重複的數字，則傳回-1；
public class Solution {
public int duplicate(int[] numbers) {
if(numbers!=null) {
int[] nums = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
if (nums[numbers[i]]==1) {
return numbers[i];
} else {
nums[numbers[i]]=1;
}
}
}
return -1;
}
}
複制
同樣這種做法的時間複雜度和空間複雜度都是
O(n)
。
那麼有沒有空間複雜度為
O(1)
的做法呢？肯定是有的，不借助額外的空間，那麼就隻能操作原數組了。如果沒有重複的情況，那麼這些數字排序後，數字i和數組下标i應該是一一對應的。不會出現多個數字
i
的情況。
基于這個原則，我們在周遊數組的時候，将元素
i
調整到下标
i
的位置，如果下标i的位置已經有元素，那麼說明沖突了，這個元素肯定是重複的，否則繼續調整後面的。如果沒有發現重複的數字，就傳回
-1
。
public class Solution {
public int duplicate(int[] numbers) {
int i = 0;
while(i < numbers.length) {
if(numbers[i] == i) {
i++;
continue;
}
if(numbers[numbers[i]] == numbers[i]) return numbers[i];
int tmp = numbers[i];
numbers[i] = numbers[tmp];
numbers[tmp] = tmp;
}
return -1;
}
}
複制
但是上面的做法，不适合求解多個重複數字的例子，因為調換的時候，很容易将後面的數字換到前面去，就會導緻求解出來不是第一個重複的數字（可以用來求解任意的重複數字），可能是第
2，3...
或者其他的重複數字。譬如：
[6,3,2,0,2,5,0]
正确的解應該是 2 ，但是由于第一次把6和最後的0調換了位置，就會導緻求解出來的值為 0 。
【作者簡介】：
秦懷，公衆号【秦懷雜貨店】作者，技術之路不在一時，山高水長，縱使緩慢，馳而不息。個人寫作方向：Java源碼解析，JDBC，Mybatis，Spring，redis，分布式，劍指Offer，LeetCode等，認真寫好每一篇文章，不喜歡标題黨，不喜歡花裡胡哨，大多寫系列文章，不能保證我寫的都完全正确，但是我保證所寫的均經過實踐或者查找資料。遺漏或者錯誤之處，還望指正。
平日時間寶貴，隻能使用晚上以及周末時間學習寫作
- END -