剑指offer算法题Java版【1】：找出数组中的重复数字

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

本文给出这道题目的4种解法，希望能够帮到你。

public class findSameNumber {
    public static void main(String args[]){
        int[] a = {2,3,1,0,2,5,3};
        System.out.println(solution4(a).toString());
    }

    public static List<Integer> solution1(int[] a){
        int temp = 0;
        Arrays.sort(a);
        List<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < a.length; i++) {
            if (a[i] != i){
                if (a[i] == a[a[i]]){
                    result.add(a[i]);
                }else {
                    temp = a[a[i]];
                    a[a[i]] = a[i];
                    a[i] = temp;
                }
            }
        }

        return result;
    }

    // 暴力法
    public static List<Integer> solution2(int[] a){
        List<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < a.length-1; i++) {
            for (int j = i+1; j < a.length; j++) {
                if (a[i] == a[j]){
                    result.add(a[i]);
                }
            }
        }

        return result;
    }

    // 利用hashset的唯一性
    public static List<Integer> solution3(int[] a){
        HashSet<Integer> hashSet = new HashSet<>();
        List<Integer> result = new ArrayList<Integer>();

        for (int value : a) {
            if (!hashSet.add(value)) {
                result.add(value);
            }
        }

        return result;
    }

    // 牺牲空间换取时间的一种方法
    public static List<Integer> solution4(int[] a){
        List<Integer> result = new ArrayList<Integer>();
        List<Integer> help = new ArrayList<Integer>(Collections.nCopies(a.length,0));

        System.out.println(help.toString());
        for (int i = 0; i < a.length; i++) {
            if (help.get(a[i])!=1){
                help.set(a[i],1);
            }else {
                result.add(a[i]);
            }
        }

        return result;
    }
}