3.数组中重复数字

题目:

在一个长度为 n 的数组里的所有数字都在0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

思路:

1.排序:O(nlogn)
2.放进hashmap: 时间O(n) 空间O(n)
3.根据0-n-1这个条件,将值为 i 的元素调整到第 i 个位置上。向后遍历
时间O(n),空间O(1)

public class RapetNum {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || numbers.length <= 0) {
            return false;
        }
        for(int i = 0; i < length; i++) {
            while(i != numbers[i]) {
                if(numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }
                swap(numbers,i,numbers[i]);
            }
        }
        return false;
    }

    private void swap(int[] numbers, int i, int j) {
        numbers[i] = numbers[i]^numbers[j];
        numbers[j] = numbers[i]^numbers[j];
        numbers[i] = numbers[i]^numbers[j];
    }

}