找出数组中的重复数字 - xiewenfeng/test GitHub Wiki

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

思路一：

重排这个数组，从头到尾扫描这个数组中的每一个元素，当下标为i时，先比较这个数字m是不是等于i 若是：接着扫描下一个 若不是：拿这个数字和下标为m的数进行比较，如果它和第m个数相等，则找到重复值，如果不相等，就把它和第m个数交换，把m放到属于它的位置上去。

private void findReapetDigital(int[] array) {
        if (array == null) return;
        int length = array.length;
        for (int i = 0; i < length; i++) {
            while (array[i] != i) {
                if (array[i] < i) {
                    System.out.println(i);
                    break;
                } else {
                    int temp = array[i];
                    array[i] = i;
                    array[temp] = temp;
                }

            }
        }
    }  

思路二：

采用辅助数组，将辅助数组全部初始化为0，当遍历原数组，原数组的值作为辅助数组下标值加1，

private int[] deduplicate(int[] array) {
        if (array == null || array.length < 1) return null;
        int length = array.length;
        int[] tempArray = new int[length];
        for (int i = 0; i < length; i++) {
            tempArray[array[i]]++;
        }
        int k = 0;
        for (int j = 0; j < length; j++ ) {
            if (tempArray[j] > 0) {
                array[k++] = j;
            }
        }
        return array;
    }

扩展：

1、如果数组不知道范围，且可能不是数字或字母 方法一：遍历数组，将元素依次添加进结果集中，若结果集中已存在，则不再添加 方法二：先将原数组排序，与相邻的进行比较，如果不同则存入新数组； 方法三：利用hashSet集合无序不可重复的特性进行元素过滤； 方法四：TreeSet不仅可以使元素不重复，还可实现排序等功能。