剑指offer：找出数组中的重复的数字Java版

题目：

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

先说一下简单的做法：

思路：

将数组排好序，再遍历数组，找到数组中的重复数字即可。使用快排

package day05;



public class test1 {
    //使用快排对数组进行排序
    public void quicksort(int[] a, int left, int right) {
        int i, j, temp, t;
        if (left > right)
            return;
        i = left;
        j = right;
        temp = a[left];
        while (i < j) {
            while (temp <= a[j] && i < j) {
                j--;
            }
            while (temp >= a[i] && i < j) {
                i++;
            }
            if (i < j) {
                t = a[j];
                a[j] = a[i];
                a[i] = t;
            }
        }
        a[left] = a[i];
        a[i] = temp;
        quicksort(a, left, j - 1);
        quicksort(a, j + 1, right);
    }

    public void change(int[] arr) {
        //找到重复的数字并打印
        for (int i = 0; i < arr.length; i++) {
            int cur = arr[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] == arr[j+1]){
                    System.out.println(arr[j] + "");
                }else
                    break;
            }
        }

    }

    public static void main(String[] args) {
        test1 t = new test1();
        int[] arr = {2, 3, 1, 0, 2, 5, 3,5};
        t.quicksort(arr, 0, arr.length - 1);
        t.change(arr);
        
    }
}

上面的代码有缺陷，因为它打印的并不仅仅是重复的数字，而是数字重复几次，就把数字打印几次，比如出现3次2，就会打印2,2,2。

第二种是基于基数排序的一种做法

//因为数字都是在0~n-1的n个数中，因此每一个数都有自己的槽位，即num[i] = num[num[i]]
//要是不相等就交换，对于交换到i的数字还要进行比较，循环，直到每个数字到达自己的槽位
//要是数字有重复，就返回num[i]。
//需要注意的就是，数字必须在0~n-1之间

public int getNum(int[] arr) {
            if (arr == null || arr.length <= 0) {
                return -1;
            }
            for (int a : arr) {
                if (a < 0 || a > arr.length - 1) {
                    return -1;
                }
            }
            for (int i = 0; i < arr.length; i++) {
                int temp;
                while (arr[i] != i) {
                    if (arr[arr[i]] == arr[i])
                        return arr[i];
                    // 交换arr[arr[i]]和arr[i]
                    temp = arr[i];
                    arr[i] = arr[temp];
                    arr[temp] = temp;
                }
            }
            return -1;
        }
    public void test() {
        int[] a = { 1, 2, 3, 2, 4 };
        int dup = getNum(a);
        if (dup >= 0)
            System.out.println("重复数字为：" + dup);
    }
 }