- ??專欄內(nèi)容：力扣刷題
- ?個人主頁：子夜的星的主頁
- ??座右銘：前路未遠(yuǎn)，步履不停
一、題目描述
1、題目
劍指offer：數(shù)組中重復(fù)的數(shù)字
在一個長度為 n 的數(shù)組里的所有數(shù)字都在 0 0 0 到 n ? 1 n-1 n?1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字重復(fù)，也不知道每個數(shù)字重復(fù)了幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。例如，如果輸入長度為7的數(shù)組 [ 2 , 3 , 1 , 0 , 2 , 5 , 3 ] [2,3,1,0,2,5,3] [2,3,1,0,2,5,3]，那么對應(yīng)的輸出是2或者3。存在不合法的輸入的話輸出-1。
數(shù)據(jù)范圍：
0
≤
n
≤
10000
0≤n≤10000
0≤n≤10000
進(jìn)階：時間復(fù)雜度
O
(
n
)
O(n)
O(n) ，空間復(fù)雜度
O
(
n
)
O(n)
O(n)
2、示例
輸入：[2,3,1,0,2,5,3]
返回值：2
說明：2或3都是對的
二、題目分析
題目的意思非常簡單，一句話總結(jié)就是：一個特定范圍內(nèi)的數(shù)組中找到任意一個重復(fù)的數(shù)字。
1、雙重for循環(huán)
public class Solution {
public static int duplicate(int[] numbers) {
for(int i =0;i<numbers.length;i++){
for (int j = i+1; j <numbers.length ; j++) {
if(numbers[i] == numbers[j])
return numbers[i];
}
}
return -1;
}
}
通過循環(huán)來比較數(shù)組中的每一對元素來查找重復(fù)。
時間復(fù)雜度是
O
(
n
2
)
O(n^2)
O(n2)：因為有兩個嵌套循環(huán)，每個循環(huán)都遍歷整個數(shù)組。
空間復(fù)雜度是
O
(
1
)
O(1)
O(1)：沒有使用除了輸入數(shù)組之外的額外空間。
2、for-each 循環(huán)
public class Solution {
public static int duplicate(int[] numbers) {
int [] res = new int[numbers.length];
for(int i:numbers){
res[i]++;
if(res[i] > 1){
return i;
}
}
return -1;
}
}
使用一個額外的數(shù)組來記錄每個數(shù)字出現(xiàn)的次數(shù)。一旦某個數(shù)字的出現(xiàn)次數(shù)超過1，就立即返回該數(shù)字。在時間上更高效，但犧牲了一些空間來達(dá)到這個目的。
時間復(fù)雜度：
O
(
n
)
O(n)
O(n)。只有一個循環(huán)，遍歷一次數(shù)組。
空間復(fù)雜度：
O
(
n
)
O(n)
O(n)。使用了一個與輸入數(shù)組同等大小的額外數(shù)組來記錄每個數(shù)字出現(xiàn)的次數(shù)。
3、set集合
public class Solution {
public static int duplicate(int[] numbers) {
Set<Integer> set = new HashSet<Integer>();
for(int i : numbers){
if(set.contains(i)){
return i;
}else{
set.add(i);
}
}
return -1;
}
}
創(chuàng)建一個 HashSet，在循環(huán)內(nèi)部，首先檢查當(dāng)前元素 i 是否已經(jīng)在 set 中：文章來源：http://www.zghlxwxcb.cn/news/detail-807075.html
- 如果
set已包含i，則返回i作為第一個重復(fù)的元素。 - 如果
set不包含i，則將i添加到set中，然后繼續(xù)循環(huán)。
時間復(fù)雜度是
O
(
n
)
O(n)
O(n)，空間復(fù)雜度是
O
(
n
)
O(n)
O(n)：使用了一個額外的 HashSet 來存儲元素。在最壞情況下（沒有重復(fù)元素），這個集合將包含所有 n 個元素。文章來源地址http://www.zghlxwxcb.cn/news/detail-807075.html
到了這里，關(guān)于【劍指offer】數(shù)組中重復(fù)的數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
