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