找出整数数组中任意重复的数字

整数数组arr大小为n，取值范围0~n-1，可能包含多个重复的数字，如果数组存在重复的数字，请找出数组arr中任意重复的数字。

思路1：使用哈希表，遍历arr，依次将arr[i]存入哈希表，如果哈希表中已经存在arr[i]，则表明arr[i]重复了。用这个方法，可以找出所有重复的数字，但是需要额外O(n)的空间，是以空间换时间。

思路2：直接修改arr数组，遍历arr，如果arr[i] != i,那么就进入一个循环，

如果arr[i] == arr[arr[i]]，则说明arr[i]出现了2次，是重复数字，可以返回了；

否则，就交换这两个数字，交换以后数字i就满足了arr[i] == i。

使用这个方法可以判断数组是否有重复数字，并且可以打印出一个重复数字，但是无法打印出所有的重复数字。

public class FindAnyDuplicateNumber {

    public int getDuplicate(int[] numbers) {

        if(numbers == null || numbers.length < 0){

            return -1;

        }

//边界条件，程序必须运行在正确的context下

for(int i = 0; i < numbers.length; i++){

if(numbers[i] <0 || numbers[i] > numbers.length){

return -1;

}

}

        for(int i = 0; i < numbers.length - 1; i++){

            while (numbers[i] != i){

                if(numbers[i] == numbers[numbers[i]]) {

                    return numbers[i];

                }

                //swap numbers[i] numbers[numberp[i]]

                int temp = numbers[i];

                numbers[i] = numbers[temp];

                numbers[temp] = temp;

            }

        }

        return -1;

    }

    public static void main(String[] args){

        //只能找到一个重复的数字，如果要找到所有重复的数字，就要使用辅助数组

        int[] nums = {1, 4, 2, 5, 2, 0, 6, 3};

        System.out.println(new FindAnyDuplicateNumber().getDuplicate(nums));

        int[] nums2 = null;

        System.out.println(new FindAnyDuplicateNumber().getDuplicate(nums2));

        int[] nums3 = {1, 4, 2, 5, 7, 0, 6, 3};

        System.out.println(new FindAnyDuplicateNumber().getDuplicate(nums3));

    }

}

---------------------

作者：翁正存

来源：CSDN

原文：https://blog.csdn.net/Wengzhengcun/article/details/86359275

版权声明：本文为博主原创文章，转载请附上博文链接！