需求分析

需求描述

现有一个ArrayList,其中包含重复元素.如果某个元素重复,只需要保留一个即可.

需求解决

主要有2种方案,一是使用for循环,二是使用HashSet.它们的成本如下:

• for循环: 时间复杂度为O(n^2)
• HashSet: 时间复杂度为O(n)
  使用HashSet明显效率更高,在数据量大的时候比较有优势.HashSet底层使用HashMap的key存储数据,利用HashMap的key不能重复的原理实现去重效果.

代码

for循环

代码如下:

    /**
     * ArrayList普通去重方法
     * @author iengchen
     * @since 2018-05-03
     */
    @Test
    public void simpleFilter() {
        
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("c");
        list.add("d");
        
        //过滤前
        for (String string : list) {
            System.out.println(string);
        }
        
        List<String> filterReapeatedList = new ArrayList<>();
        for (String string : list) {
            if (!filterReapeatedList.contains(string)) {
                filterReapeatedList.add(string);
            }
        }
        
        //过滤后
        System.out.println("====== 过滤后 ======");
        for (String string : filterReapeatedList) {
            System.out.println(string);
        }   
        
    }

HashSet

代码如下:

/**
     * ArrayList使用HashSet去重
     * @author iengchen
     * @since 2018-05-03
     */
    @Test
    public void hashsetFilter() {
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("c");
        list.add("d");
        
        //过滤前
        for (String string : list) {
            System.out.println(string);
        }
        
        HashSet<String> set = new HashSet<>(list);
        List<String> filterReapeatedList = new ArrayList<>(set);
        //过滤后
        System.out.println("====== 过滤后 ======");
        for (String string : filterReapeatedList) {
            System.out.println(string);
        }   
    
    }

测试结果

上面2个方案中的测试结果都是:

a
b
a
b
c
d
c
d
====== 过滤后 ======
a
b
c
d