数组中重复的数字

解法一：

• 时间复杂度O(N)，空间复杂度O(N)

import java.util.*;

public class Solution {
    public int duplicate (int[] a) {
        int[] b = new int[a.length]; // 辅助数组，其下标代表值，数值代表出现次数
        for (int i = 0; i < a.length; i++) {
            if (b[a[i]] == 0) b[a[i]]++;
            else return a[i];
        }
        return -1;
    }
}

解法二：

• 《剑指Offer》官方答案，就地交换，每一个数字交换不会超过2次
• 时间复杂度O(N)，空间复杂度O(1)

import java.util.*;

public class Solution {
    public int duplicate (int[] a) {
        for (int i = 0; i < a.length; i++) {
            while (a[i] != i) {
                if (a[i] == a[a[i]]) return a[i];
                else {
                    int tmp = a[a[i]];
                    a[a[i]] = a[i];
                    a[i] = tmp; 
                }
            }
        }
        return -1;
    }
}