数组中重复的数字

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || length == 0) return false; 
        for (int i=0; i<length; ++i) {
            if (numbers[i] == i) continue; // 位置正确, 跳过
            if (numbers[i] != numbers[numbers[i]]) { // 如果数字和它应该去的位置上的数不一样就交换
                int tmp = numbers[i];
                numbers[i] = numbers[tmp];
                numbers[tmp] = tmp;
            } else {
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }

思路

1.hash

很简单，遍历用hash保存和判断即可，不浪费口舌。

2.额外数组

由于数字在n->n-1范围，新建一个长度为n的数组来记录每个遍历的元素，检测到记录过的数字即为第一个重复数字。原理和hash其实没区别。

3.无额外空间（略复杂）

由于数字0->n-1，可将当前数字与数组中以该数字为坐标的数交换，如果发现以该数字为坐标的数等于当前数字，则重复。
eg：[2,1,3,1,4]，
i=0时，将i=0和i=2交换->[3,1,2,1,4]
i=1，不变；
i=2，不变；
i=3，发现number[3](即1)与number[number[3]]（即1）相同，即第一个重复数字。

代码

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (length <= 1) return false;
        for (int i = 0; i < numbers.length; i++) {
            if (i == numbers[i]) continue; // 删去也无所谓，能省一点不必要的计算
            if(numbers[i] == numbers[numbers[i]] && numbers[i] != i) {
                duplication[0] = numbers[i];
                return true;
            }
            swap(numbers, i, numbers[i]);
        }
        return false;
    }

    public static void swap(int[] arr, int a, int b) {
        arr[a] ^= arr[b];
        arr[b] ^= arr[a];
        arr[a] ^= arr[b];
    }

import java.util.HashSet;
public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    if(numbers==null || numbers.length==0){
        return false;
    }
        boolean flag=false;
        int a=0;
        for(int i=0;i<numbers.length;i++){
            for(int j=i+1;j<numbers.length;j++){
                if(numbers[i]==numbers[j]){
                    flag=true;
                    a=numbers[i];
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        if(flag){
            duplication[0]=a;
            return flag;
        }
        return flag;
    }
}

// 解法一：使用hash表（hashmap），遍历数组找到重复的数字即返回true。时间复杂度O（n），空间复杂度O（n）
// 略
// 解法二：利用题目的特性，重复数字不指定，值范围在0~n-1。时间复杂度O（n），空间复杂度O（1）


 
 public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (numbers == null || numbers.length <= 0) {
            return false;
        }
        // 验证输入数组值是否正确
        for (int i = 0; i< length ; i++) {
            if (numbers[i] > length - 1 || numbers[i] < 0) {
                return false;
            }
        }
        // 将下标未i对应的数字m移到m位置上
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == i ) {
                continue;
            }
            // 要一直循环，知道找到下标和值相同的位置
            while(numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[i] = numbers[i];
                    return true;
                }
                int temp = numbers[numbers[i]];
                numbers[numbers[i]] = numbers[i];
                numbers[i] = temp;
            }
        }
        return false;
    }
}

    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if (length <= 0) {
            return false;
        }
        // 因为数组里的所有数字都在0到n-1的范围内
        int count[] = new int[length];
//        Arrays.fill(count, 0);, int 的默认值就是 0
        int a;
        for (int i = 0; i < length; i++) {
            a = numbers[i];
            count[a] ++;
            if (count[a] == 2) {
                // 这个数字前面已经出现过一次，现在出现第二次记录到 duplication 数组中
                // PS : length of duplication array is 1
                duplication[0] = a;
                return true;
            }
            // 该数字已经出现多次（count[a] > 2）, 不需要做过多的其他处理
        }
        return false;
    }

public static int getNumber(int[] ints){
        //定义一个与数组长度相同的boolean数组
        boolean[] booleans = new boolean[ints.length];
        //遍历数组中的每个数，将遍历的数作为boolean的索引
        for (int i = 0; i < ints.length; i++) {
            //判断boolean索引的元素是否是fales，如果是则更改为true，反之直接返回当前的索引，即为重复的数字。
            if (booleans[ints[i]] != true){
                booleans[ints[i]] = true;
            }else {
                return ints[i];
            }
        }
        return -1;
    }

/*
须注意到数组中值的范围。
关键是加上length后，也能得到数组原来存储的数值。，只需要减掉一个length即可。
*/
public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        for (int i=0;i<length;i++) {
            int num = numbers[i];
            if (num >= length) {
                num -= length;
            }
            if (numbers[num] >= length) {
                duplication[0] = num;
                return true;
            } else {
                numbers[num] += length;
            }
        }
        return false;
    }
}

/*

*/

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i=0;i<length;i++) {
            if (!set.add(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) {
        if (length==0){
            return false;
        }
        Arrays.sort(numbers);
        for(int i=0;i<length-1;i++){
            if(numbers[i]==numbers[i+1]){
                duplication[0]=numbers[i];
                return true;
            }
        }
        return false;
    }
}

import java.util.Arrays;

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length > 0)
            Arrays.sort(numbers);
        int n = -1;
        for(int i = 0; i < length;i++){
            if((i + numbers[0]) != numbers[i]){
                n = numbers[i];
                break;
            }
        }
        duplication[0] = n;
        if(n != -1){
            return true;
        }
        return false;
    }
}