【六种方式】去除数组中的重复元素

????1. 问题描述

• 给定一个数组，判断数组中的元素是否重复？

• 给定为整型数组，或者字符串去重？

• 不使用集合类，怎么去重？

• 不使用集合类，怎么保证【稳定】去重？

????2. 思路探究

判断是否有重复

• 集合类的contains()方法
• 计数排序

去重复

• Set集合
• 排序 + 双指针（稳定或不稳定）
• 枚举 + 标志位

????3. 代码实现

集合类直接在放入时判断是否包含即可

排序 + 双指针

先对数组中的序列排序

[1, 1, 2, 3, 3, 5, 5, 5, 7, 8, 9, 9]

然后双指针将不重复元素放入新的结果集res数组中

怎么保证稳定

• 使用归并排序（稳定排序）
• 遇到重复元素，选取第一次出现的位置（保证稳定）

$1_i$1i​、$1_j$1j​，选$1_i$1i​

class Solution {
	/**
     * 【归并排序 + 双指针】
     *
     * @param arr
     * @return
     */
    public static int[] removeRepeat_sort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
        int slow = 0, fast = 1;
        while (fast < arr.length) {
            if (arr[slow] != arr[fast]) {
                slow++;
                arr[slow] = arr[fast];
            }
            fast++;
        }
        int[] res = new int[slow + 1];
        for (int i = 0; i < slow + 1; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    private static void mergeSort(int[] arr, int low, int high) {
        if (low >= high) return;
        int pivot = (low + high) >>> 1;
        int temp[] = new int[arr.length];
        mergeSort(arr, low, pivot);
        mergeSort(arr, pivot + 1, high);
        merge(arr, low, pivot, high, temp);
    }

    private static void merge(int[] arr, int low, int pivot, int high, int[] temp) {
        int p1 = low, p2 = pivot + 1;
        int index = low;
        while (p1 <= pivot && p2 <= high) {
            temp[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= pivot) temp[index] = arr[p1++];

        while (p2 <= high) temp[index] = arr[p2++];

        for (int i = low; i <= high; i++) {
            arr[i] = temp[i];
        }
    }
}

双层循环枚举 + 标志位

1. 首先建立一个与原数组等长的标记数组flag[]，它的下标与原数组下标相同，而我们只要改变它的值，就可以知道第几个元素是重复的
2. 遍历原数组 内层也遍历原数组，如果arr[i] == arr[j]，也就是外层循环到的元素与内层循环的相等 （内层是从 i+1 开始找）
3. 循环结束后 ，flag数组求和，就是重复元素的个数，用原数组长度减去它，就等到了新数组的长度。声明一个变量表示所求新数组的下标 index，如果flag[i] == 0 ，那么 将所对应原数组的值赋给新数组 newArr[index++] = arr[i]

class solution {
	//【方法一】 需要传入一个Object数组，然后返回去重后的数组
    public static Object[] ifRepeat(int[] arr) {
        //用来记录去除重复之后的数组长度和给临时数组作为下标索引
        int t = 0;
        //临时数组
        Object[] tempArr = new Object[arr.length];
        //遍历原数组
        for (int i = 0; i < arr.length; i++) {
            //声明一个标记，并每次重置
            boolean isTrue = true;
            //内层循环将原数组的元素逐个对比
            for (int j = i + 1; j < arr.length; j++) {
                //如果发现有重复元素，改变标记状态并结束当次内层循环
                if (arr[i] == arr[j]) {
                    isTrue = false;
                    break;
                }
            }
            //判断标记是否被改变，如果没被改变就是没有重复元素
            if (isTrue) {
                //没有元素就将原数组的元素赋给临时数组
                tempArr[t] = arr[i];
                //走到这里证明当前元素没有重复，那么记录自增
                t++;
            }
        }
        //声明需要返回的数组，这个才是去重后的数组
        Object[] newArr = new Object[t];
        //用arraycopy方法将刚才去重的数组拷贝到新数组并返回
        System.arraycopy(tempArr, 0, newArr, 0, t);
        return newArr;
    }
}

数组覆盖

1. System类方法System.arraycopy(arr, k+1, arr, k, arr.length-k-1) 让重复元素之后的数组元素往前挪一个，使得重复数字被覆盖。
2. 再删除最后一个元素 （因为复制粘贴的时候最后一个没有被覆盖而是保持原来的值）

class Solution {
	public static int[] deRepetition(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; ) {
                if (arr[i] == arr[j]) {
                    System.arraycopy(arr, j + 1, arr, j, arr.length - j - 1);
                    //缩容的同时相当于删除了最后一个元素
                    arr = Arrays.copyOf(arr, arr.length - 1);
                    //发现重复元素时jk++
                } else {
                    j++;
                    //没有重复元素才与后一个数比较
                }
            }
        }
        return arr;
    }
}

计数排序判断

计数排序判断是否有重复元素

【辅助数组容量确定】

• 整型元素：[0…9]，capacity = 10
• 字符型元素：capacity = 128

以字符为例

	public static boolean isRepeated(String s) {
        int[] count = new int[128];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)]++;
            if(count[s.charAt(i)] > 1) {
                return true;
            }
        }
        return false;
    }

---

【文章参考】

• java中去除数组中重复元素的方法
• 去除数组重复元素的方法