春风博客

春天里,百花香...

导航

<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

判断数组元素是否存在重复,要求时间复杂度为O(1)

下面的代码涉及判断数组元素是否存在重复,要求时间复杂度为O(1)。
这样的题肯定不能用双循环比较,这样太慢,用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,无重复结果

posted on 2008-06-11 11:44 sitinspring 阅读(3060) 评论(1)  编辑  收藏 所属分类: Java基础算法数据结构

评论

# re: 判断数组元素是否存在重复,要求时间复杂度为O(1) 2013-07-12 14:43 Ricky

这个时间复杂度不是O(1)吧,HashSet内吧的判定也影响时间复杂度的!  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.