信手拈来 妙手偶得 » 日志 » 【原创】判断数组元素是否存在重复，要求时间复杂度为O(n)
【原创】判断数组元素是否存在重复，要求时间复杂度为O(n)
Junglesong 发表于 2008-06-11 21:43:05
下面的代码涉及判断数组元素是否存在重复，要求时间复杂度为O(n)。
这样的题肯定不能用双循环比较，这样太慢，用hashcode判断是正道，使用现成的hashset更能简化代码。
代码如下：
package com.sitinspring;
import java.util.HashSet;
import java.util.Set;
/** *//**
* 数组重复测试，要求时间复杂度为O（n）
* @author sitinspring（junglesong@gmail.com）
* @since 2008-6-11 上午11:12:53
* @vsersion 1.00 创建 sitinspring 2008-6-11 上午11:12:53
*/
public class ArrayDuplicateTest
{
/** *//**
* 构造函数
*
*/
public ArrayDuplicateTest(int[] arr){
System.out.print("数组:");
for(int temp:arr){
System.out.print(temp+",");
}
if(hasDuplicateItem(arr)==false){
System.out.println("无重复结果");
}
else{
System.out.println("有重复结果");
}
}
/** *//**
* 取得检测结果
* @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);
}
}
输出：
数组:1,2,3,4,5,无重复结果
数组:1,2,3,4,5,5,53,43,42,2,454,6,5456,4534,4,有重复结果
数组:1,2,3,4,5,767,4332,534,76,6583,356,无重复结果
这样的题肯定不能用双循环比较，这样太慢，用hashcode判断是正道，使用现成的hashset更能简化代码。
代码如下：
package com.sitinspring;import java.util.HashSet;import java.util.Set;/** *//** * 数组重复测试，要求时间复杂度为O（n） * @author sitinspring（junglesong@gmail.com） * @since 2008-6-11 上午11:12:53 * @vsersion 1.00 创建 sitinspring 2008-6-11 上午11:12:53 */public class ArrayDuplicateTest{ /** *//** * 构造函数 * */ public ArrayDuplicateTest(int[] arr){ System.out.print("数组:"); for(int temp:arr){ System.out.print(temp+","); } if(hasDuplicateItem(arr)==false){ System.out.println("无重复结果"); } else{ System.out.println("有重复结果"); } } /** *//** * 取得检测结果 * @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); }}输出：
数组:1,2,3,4,5,无重复结果数组:1,2,3,4,5,5,53,43,42,2,454,6,5456,4534,4,有重复结果数组:1,2,3,4,5,767,4332,534,76,6583,356,无重复结果
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾