下面的代碼涉及判斷數(shù)組元素是否存在重復(fù)，要求時(shí)間復(fù)雜度為O(1)。
這樣的題肯定不能用雙循環(huán)比較，這樣太慢，用hashcode判斷是正道，使用現(xiàn)成的hashset更能簡(jiǎn)化代碼。
代碼如下：
package com.sitinspring;
import java.util.HashSet;
import java.util.Set;
/** *//**
* 數(shù)組重復(fù)測(cè)試，要求時(shí)間復(fù)雜度為O（n）
* @author sitinspring（junglesong@gmail.com）
* @since 2008-6-11 上午11:12:53
* @vsersion 1.00 創(chuàng)建 sitinspring 2008-6-11 上午11:12:53
*/
public class ArrayDuplicateTest
{
/** *//**
* 構(gòu)造函數(shù)
*
*/
public ArrayDuplicateTest(int[] arr){
System.out.print("數(shù)組:");
for(int temp:arr){
System.out.print(temp+",");
}
if(hasDuplicateItem(arr)==false){
System.out.println("無重復(fù)結(jié)果");
}
else{
System.out.println("有重復(fù)結(jié)果");
}
}
/** *//**
* 取得檢測(cè)結(jié)果
* @param arr
* @return
*/
private boolean hasDuplicateItem(int[] arr){
Set<Integer> set=new HashSet<Integer>();
for(int i:arr){
if(!set.add(i)){
return true;
}
}
return false;
}
public static void main(String[] args){
int[] arr1={1,2,3,4,5};
new ArrayDuplicateTest(arr1);
int[] arr2={1,2,3,4,5,5,53,43,42,2,454,6,5456,4534,4};
new ArrayDuplicateTest(arr2);
int[] arr3={1,2,3,4,5,767,4332,534,76,6583,356};
new ArrayDuplicateTest(arr3);
}
}
輸出：
數(shù)組:1,2,3,4,5,無重復(fù)結(jié)果
數(shù)組:1,2,3,4,5,5,53,43,42,2,454,6,5456,4534,4,有重復(fù)結(jié)果
數(shù)組:1,2,3,4,5,767,4332,534,76,6583,356,無重復(fù)結(jié)果