找出数组中重复的元素题目：解法：代码：

63 阅读 0 评论 42 点赞

我是靠谱客的博主帅气玉米，最近开发中收集的这篇文章主要介绍找出数组中重复的元素题目：解法：代码：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

int[] array, length of array is k, [0, k-1]
实现函数：void printDup(int[] array, int k)，打印重复元素，不限顺序；一个元素若出现多次，可打印多次。
输入：array = [2,2,1,1], k = 4
输出：
2
1

解法：

思路1：维护一个HashSet，存储出现过的元素。空间复杂度O(N)，时间复杂度O(N)

思路2：由于数组元素的值在0~k-1之间，可以维护一个int数组times用于记录元素出现的次数。比如times[i]=3，表名i在array中出现三次。最后打印出所有array[i] != 0的i。空间复杂度O(N)，时间复杂度O(N)

思路3：由于这里只要求打印重复的元素，不要求具体的次数，可以将int[] times -> boolean[] isDup，空间复杂度O(N)，时间复杂度O(N)，但空间使用明显减少。

思路4：考虑进一步降低思路3的空间复杂度，在原数组的基础上通过将下表为i的元素置为负，来表名i重复，比如：array[i] = x -> array[i] = -x，表明元素i已出现。空间复杂度O(N)，时间复杂度O(1)。如果需要将原数组复原，则最后需要扫描一遍array，将-x取正

加入额外限制条件：算法过程中不允许数组元素超越0~k-1的范围

思路5：由于不能将元素取负，通过交换数组元素，考虑将array[i]的值设置为i，最后遍历数组，当array[i] != i时，则表明i重复。空间复杂度O(N)，时间复杂度O(1)

代码：

采用思路5的java代码如下：

public void printDup(int[] array, int k) {
    if (k <= 1) {
        return;
    }
    // 尝试将下标为i的值置为i
    for (int i = 0; i < k; ) {
        int index = array[i];
        if (array[index] != index) {
        // 不会死循环：因为index是有限的，swap后，array[index] = index，因此一定能遇到array[index] == index的情况
        // 如：2,2,1,1 -> 1,2,2,1 -> 2,1,2,1
            swap(array, i, index);
        } else {
            i++;
        }
    }

    for (int i = 0; i < k; i++) {
        if (array[i] != i) {
            System.out.println(array[i]);
        }
    }
}
private void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}