題目要求
在一個長度為n的數(shù)組里所有數(shù)都在0-n之間，數(shù)組中存在重復(fù)的數(shù)吭狡，但是不知道幾個數(shù)字重復(fù)了，也不知道數(shù)字重復(fù)了幾次丈莺，請找出數(shù)組中任意一個重復(fù)的數(shù)字划煮。
題目解析
思路一：
- 分析
利用hashMap，key值只能存在一個的特點缔俄。將數(shù)組中的數(shù)字以其值作為其key值弛秋，進行逐個存儲
在存儲之前查找之前有沒有以此值為key的鍵值對，如果有俐载，則可以得到重復(fù)的第一個數(shù)字蟹略。
優(yōu)點，時間復(fù)雜度低O(1)遏佣，最多只需要進行n次存儲挖炬。
缺點，空間復(fù)雜度較高O(n)
由于題目說明了數(shù)據(jù)大于0,所以我們可以使用-1作為錯誤標記
- 代碼段
public int demo1( int[] datas) {
Map<Integer , Integer> dataMap = new HashMap<>();
//判非空
if(datas == null || datas.length == 0) {
return -1 ;
}
//查詢數(shù)據(jù)是否規(guī)范
for(int data : datas) {
if(0 > data || data > datas.length-1) {
return -1 ;
}
}
//得到并返回第一個重復(fù)值
for(int data : datas) {
if(dataMap.get(data) != null) {
return data ;
}
dataMap.put(data, data) ;
}
//數(shù)組中不存在重復(fù)值
return -2;
}
思路二：
- 分析
思路二：
題中提到贼急，數(shù)組中的數(shù)都在0-n之間茅茂，既然他是數(shù)組，那么我們就可以利用數(shù)組下標進行文章太抓。
從0開始遍歷數(shù)組空闲，設(shè)下標為i，下標為i的數(shù)字的值是m走敌。
如果i==m遍歷下一個碴倾。
如果i!=m，查找下標為m的值，并與m比較跌榔，若相同异雁，則m為第一個重復(fù)的值，若不同僧须，將下標為i的值與下標為m的值相互調(diào)換纲刀。
繼續(xù)對比此時i與m，重復(fù)以上担平，直到找到第一個重復(fù)值示绊。
由于題目說明了數(shù)據(jù)大于0,所以我們可以使用-1作為錯誤標記
時間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
- 代碼段
public int demo2( int[] datas) {
//判非空
if(datas == null || datas.length == 0) {
return -1 ;
}
//查詢數(shù)據(jù)是否規(guī)范
for(int data : datas) {
if(0 > data || data > datas.length-1) {
return -1 ;
}
}
//進行循環(huán)查找
for(int temp , m , i = 0 ; i < datas.length ; ) {
m = datas[i] ;
if(m == i) {
i++;
continue ;
}else if(m == datas[m]){
return m ;
}else if(m!= datas[m]) {
temp = datas[i] ;
datas[i] = datas[m];
datas[m] = temp ;
}
}
//數(shù)組中不存在重復(fù)值
return -2 ;
}
測試代碼：
public static void main(String[] args) {
int[] datas1 = {3,2,1,4,5,2,1,7} ;
int[] datas2 = null ;
int[] datas3 = {1,2,3,4,5,0};
int[] datas4 = {1,12,15,46} ;
int result = 0 ;
demo d1 = new demo() ;
result = d1.demo1(datas1) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo1(datas2) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo1(datas3) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo1(datas4) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo2(datas1) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo2(datas2) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo2(datas3) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
result = d1.demo1(datas4) ;
System.out.println((result == -1)? "數(shù)組為空或者不符合規(guī)范" : ((result == -2) ? "數(shù)組中不存在重復(fù)值":"重復(fù)的第一個數(shù)字是："+ result) );
}
運行結(jié)果
重復(fù)的第一個數(shù)字是：2
數(shù)組為空或者不符合規(guī)范
數(shù)組中不存在重復(fù)值
數(shù)組為空或者不符合規(guī)范
重復(fù)的第一個數(shù)字是：2
數(shù)組為空或者不符合規(guī)范
數(shù)組中不存在重復(fù)值
數(shù)組為空或者不符合規(guī)范
