数组 List 去除重复数据多种实现及性能分析

傷城~ 2022-12-22 09:26 127阅读 0赞

## 数组 有序的情况下去重 ##

有序的情况下只要将每一个元素与已经去重的数组的最后一个对比相等就下一个元素，不相等就赋值到已去重的后一位

public int removeDuplicates(int[] nums) { 
            if (nums.length == 0) { 
                return 0;
            }
            int i = 0;
            //从第二个元素开始遍历整个数组
            for (int j = 1; j < nums.length; j++) { 
                //如果后面一个元素等于已经保存的nums[i]（已经去重的数组的最后一个元素），遍历继续
                //不相等才回去++i将元素移动到nums[i]，
                if (nums[j] != nums[i]) { 
                    i++;
                    nums[i] = nums[j];
                }
            }
            return i + 1;
        }

时间复杂度：O(n)，假设数组的长度是 n，那么 i和 j 分别最多遍历 n 步。  
空间复杂度：O(1)。

## 数组 无序去重 ##

**双层指针法（两层for循环）**

public static int removeDuplicates(int[] nums) { 
            int count=0;
            for (int i = 0; i < nums.length-count; i++) { 
                for (int j = i+1; j < nums.length-count;  ) { 
                    //相等，移除nums[j]
                    if (nums[i]==nums[j]){ 
                        System.arraycopy(nums, j+1, nums, j, nums.length-j-1);
                        count++;
                    }else { 
                        j++;
                    }
                }
            }
            //返回不重复的元素个数
            return nums.length-count;
        }

很明显这效率是不高的。  
时间复杂度：O(n²)，假设数组的长度是 n，那么 i最多走n 步， j 最多走 n\*n 步。  
空间复杂度：O(1)。  
甚至效率不如先排序再去重

**空间换时间**，定义一个足够大的数组，下标代表元素值，对应的值代表元素出现的次数

public static int removeDuplicates(int[] nums) { 
            int[] tem = new int[100];
            for (int num : nums) { 
                tem[num] = tem[num] + 1;
            }
            int index = 0;
            for (int i=0;i<tem.length;i++){ 
                if (tem[i]>0){ 
                    nums[index] = i;
                    index++;
                }
            }
            return index;
        }

有限制  
时间复杂度O(n)，只需要遍历nums和临时数组  
仅适用于，知晓数组内最大元素的情况使用

## List去重 ##

以上两种方式就不赘述了，相等就调用remove方法移除即可。看几种实现已有API的方法实现。

*  使用List集合contains方法循环遍历

public static Collection removeDuplicates(Collection<Integer> list) { 
            List<Integer> res = new ArrayList<>();
            for (Integer integer:list){ 
                if (!res.contains(integer)){ 
                    res.add(integer);
                }
            }
            return res;
        }

时间复杂度：O(n²)，contains方法要遍历一遍数组  
空间复杂度：O(n)

*  使用HashSet实现List去重

public static Collection<Integer> removeDuplicates(Collection<Integer> list) { 
        return new HashSet<>(list);
    }

HashSet底层聚合了个HashMap，利用key的不重复性，相当于调用for循环，一个个put元素  
时间复杂度：O(n)~O（n²），put元素，最好的情况O（1），最差的情况下O（n），冲突严重全是链表的情况（比较少）  
空间复杂度：O(n)

*  使用TreeSet实现List去重

public static Collection<Integer> removeDuplicates(Collection<Integer> list) { 
        return new TreeSet<>(list);
    }

*  使用java8新特性stream实现List去重

public static List removeDuplicates(List<Integer> list) { 
            return list.stream().distinct().collect(Collectors.toList());
        }

它是基于hashCode（）和equals（）工作的；判断两个对象是否相同原理与HashMap定位key原理相同，先计算hashCode，如果hashCode相同继续调用equals()方法。  
时间复杂度：O(n)~O（n²），put元素，最好的情况O（1），最差的情况下O（n），冲突严重全是链表的情况（比较少）  
空间复杂度：O(n)