数组中重复的数字

解法一

遍历比较数组元素，判断是否有重复。
时间 。

public class Solution {
    public boolean duplicate(int[] numbers, int length, int[] duplication) {
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (numbers[j] == numbers[i]) {
                    duplication[0] = numbers[i];
                    return true;
                }
            }
        }
        return false;
    }
}

解法二

利用哈希表，遍历数组，如果哈希表中没有该元素，则存入哈希表中，否则返回重复的元素。
时间 ，空间 。

import java.util.*;

public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < length; i++) {
            if (set.contains(numbers[i])) {
                duplication[0] = numbers[i];
                return true;
            } else {
                set.add(numbers[i]);
            }
        }
        return false;
    }
}

解法三

时间 ，空间 。

长度为 n，元素的数值范围也为 n，如果没有重复元素，那么数组每个下标对应的值与下标相等。从头到尾遍历数组，当扫描到下标 i 的数字 nums[i]，如果：

• nums[i] = i，继续向下扫描；
• nums[i] ≠ i，拿它与第 nums[i] 个数进行比较，如果：
  • 相等，说明有重复值，返回 nums[i]。
  • 不相等，就把第 i 个数 和第 nums[i] 个数交换。重复这个比较交换的过程。

public class Solution {
    public boolean duplicate(int[] numbers, int length, int[] duplication) {
        if (numbers == null || length < 1) {
            System.out.println("数组输入无效");
            return false;
        }
        for (int e : numbers) {
            if (e >= length) {
                System.out.println("数字大小超出范围！");
                return false;
            }
        }

        for (int i = 0; i < length; ++i) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    System.out.println("重复数字：" + duplication[0]);
                    return true;
                }
                int tmp = numbers[i];
                numbers[i] = numbers[tmp];
                numbers[tmp] = tmp;
            }
        }
        System.out.println("数组中无重复数字！");
        return false;
    }
}

测试用例

1. 长度为 n 的数组中包含一个或多个重复的数字；
2. 数组中不包含重复的数字；
3. 无效测试输入用例（输入空指针；长度为 n 的数组中包含 0~n-1 之外的数字）。

public static void main(String[] args) {
    Solution s = new Solution();
    int[] a = {2, 3, 1, 0, 2, 5, 3};
    //int[] a = {2, 3, 1, 0, 4, 5, 6};
    //int[] a = null;
    //int[] a = {2, 3, 1, 0, 4, 5, 9};
    int b = a.length;
    int[] c = new int[1];
    s.duplicate(a, b, c);
}