判斷集合中存在重復(fù)是常見(jiàn)編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時(shí)我們通常希望少進(jìn)行幾次掃描，這時(shí)雙重循環(huán)法就不可取了。
位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創(chuàng)建一個(gè)長(zhǎng)度為max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上1，如遇到5就給新數(shù)組的第六個(gè)元素置1，這樣下次再遇到5想置位時(shí)發(fā)現(xiàn)新數(shù)組的第六個(gè)元素已經(jīng)是1了，這說(shuō)明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這種給新數(shù)組初始化時(shí)置零其后置一的做法類(lèi)似于位圖的處理方法故稱(chēng)位圖法。它的運(yùn)算次數(shù)最壞的情況為2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長(zhǎng)的話效率還能提高一倍。
示例代碼如下：
package com.sitinspring;
/** *//**
* 數(shù)組重復(fù)探測(cè)，時(shí)間復(fù)雜度為O（n）
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-6-18-上午03:24:07
*/
public class DuplicatedArrayTest
{
public static void main(String[] args){
int[][] arr={
{1,2,3,5,3,5,56,534,3,32},
{1,2,3,5},
{1,2,3,5,3,5},
{0,0,1,2,3,5,56,534,78,32},
};
for(int i=0;i<arr.length;i++){
System.out.print("數(shù)組:");
for(int temp:arr[i]){
System.out.print(temp+",");
}
System.out.print("中");
System.out.print(hasDuplicatedItem(arr[i])?"存在":"不存在");
System.out.print("重復(fù)元素.\n");
}
}
/** *//**
* 判斷整形數(shù)組中是否有重復(fù)數(shù)據(jù)，時(shí)間復(fù)雜度為O（n）
* @param arr
* @return
*/
public static boolean hasDuplicatedItem(int[] arr){
// 掃描數(shù)組找最大值
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>max){
max=arr[i];
}
}
// 按最大值創(chuàng)建一個(gè)新數(shù)組
int[] bitArray=new int[max+1];
// 按值向新數(shù)組中添值，如value為3則bitArray[3]=1
for(int value:arr){
if(bitArray[value]!=0){
// 如果value指向的位置已經(jīng)不是零，說(shuō)明之前已經(jīng)給這一塊置1了，立即返回true表示數(shù)組有重復(fù)
return true;
}
else{
// value指向的位置是零,則置為1表示這一位已經(jīng)有數(shù)存在了
bitArray[value]=1;
}
}
return false;
}
}
輸出：
數(shù)組:1,2,3,5,3,5,56,534,3,32,中存在重復(fù)元素.
數(shù)組:1,2,3,5,中不存在重復(fù)元素.
數(shù)組:1,2,3,5,3,5,中存在重復(fù)元素.
數(shù)組:0,0,1,2,3,5,56,534,78,32,中存在重復(fù)元素.
題外話：
今天法國(guó)真是太背了，為它送行吧！但愿它能早日迎來(lái)一個(gè)新的齊達(dá)內(nèi)。