每日算法（1）——数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 到 n - 1 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字 2。

解法1：

数组排序，比较相邻元素是否相等。时间复杂度为 O(nlogn)，空间复杂度为 O(1)。

解法2：

利用 HashSet 解决，时间复杂度为 O(n)，空间复杂度也为 O(n)。

    public static boolean duplicateHashSet(int[] array) {
        if (array == null || 0 == array.length)
            return false;

        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1)
                return false;
        }

        Set<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (!hashSet.add(array[i])) {
                System.out.println(array[i]);
                return true;
            }
        }

        return false;
    }

解法3：

特殊解法，遍历数组，假设第 i 个位置的数字为 j，则通过交换将 j 换到下标为 j 的位置上，直到所有数字都出现在自己对应的下表处，或发生了冲突。代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度为 O(n)。所有操作都是在数组上进行的，不需要额外分配内存，因此空间复杂度为 O(1)。

    // 可输出所有重复的元素
    public static Collection duplicate(int[] array, Collection<Integer> c) {
        if (array == null || 0 == array.length)
            return null;

        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1)
                return null;
        }

        for (int i = 0; i < array.length; i++) {
            while (array[i] != i) {
                if (array[i] == array[array[i]]) {
                    System.out.println(array[i]);
                    c.add(array[i]);
                    break;
                }
                int tmp = array[i];
                array[i] = array[tmp];
                array[tmp] = tmp;
            }
        }

完整代码

import java.util.*;

public class RepeatNum {
    public static int[] array;
    public static Collection<Integer> collection;

    public static boolean duplicateHashSet(int[] array) {
        if (array == null || 0 == array.length)
            return false;

        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1)
                return false;
        }

        Set<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (!hashSet.add(array[i])) {
                System.out.println(array[i]);
                return true;
            }
        }

        return false;
    }

    public static Collection duplicate(int[] array, Collection<Integer> c) {
        if (array == null || 0 == array.length)
            return null;

        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1)
                return null;
        }

        for (int i = 0; i < array.length; i++) {
            while (array[i] != i) {
                if (array[i] == array[array[i]]) {
                    System.out.println(array[i]);
                    c.add(array[i]);
                    break;
                }
                int tmp = array[i];
                array[i] = array[tmp];
                array[tmp] = tmp;
            }
        }

        return c;
    }

    public static void main(String[] args) {
        array = new int[]{2, 3, 1, 0, 2, 5, 3};
        collection = new ArrayList<>();
        collection = duplicate(array, collection);
        boolean bb = duplicateHashSet(array);
        System.out.println(collection.toString());
        System.out.println(bb);
    }
}