本文共 1955 字，大约阅读时间需要 6 分钟。

题目描述

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

分析

思路1：直接将数组进行排序，再进行遍历统计是否出现重复数字。排序的时间复杂度为$O(nlogn)$。

思路2：对数组进行一次遍历，使用Map容器将数字及其出现的数字存储起来。在$O(n)$时间内遍历数组，利用了$O(n)$的辅助空间能够在$O(1)$时间内找到是否有重复数字。总的时间复杂度为$O(n)$。

思路3：由于数组长度为n，每一个数字的范围为[1,n-1]，那么如果数组中不存在重复的数字，则数组在递增排序的情况下，数组的索引值等于对应的数值，即numbers[i] = i；如果有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。

现在对数组进行扫描，当扫描到下标为i的数字时，首先比较这个数字（m）是否等于i，如果是，则扫描下一个数字；否则，将这个数字m和索引值为m的数字进行比较，如果相等，则找到重复的数字，返回true，否则将m和索引值为m的数字交换，则i索引位置上得到新的m，重复这个比较和交换的过程，直到发现重复数字为止。

牛客AC：

package com.problem;public class FindDuplicationNumber {
       public static void main(String[] args) {        FindDuplicationNumber findDuplicationNumber = new FindDuplicationNumber();        int[] numbers = {
  2,3,1,0,2,5,3};        int[] duplication = new int[1];        System.out.println(findDuplicationNumber.duplicate(numbers, numbers.length, duplication));        System.out.println(duplication[0]);    }    //  这里要特别注意~返回任意重复的一个，赋值duplication[0]    public boolean duplicate(int numbers[],int length,int [] duplication) {        if(numbers == null || numbers.length <= 0 || numbers.length != length)            return false;        for(int i = 0; i < length; i++) {            if(numbers[i] < 0 || numbers[i] > length - 1)                return false;        }        for(int i = 0; i < length; i++) {            while(numbers[i] != i) {                if(numbers[i] == numbers[numbers[i]]) {                    duplication[0] = numbers[i];                    return true;                }                swap(numbers, i, numbers[i]);            }        }        return false;    }    // 不使用辅助空间和新的变量进行交换    // 使用数组传址的方式，交换的结果才能保留。    public void swap(int[] numbers, int i, int j) {        numbers[i] = numbers[i] ^ numbers[j];        numbers[j] = numbers[i] ^ numbers[j];        numbers[i] = numbers[i] ^ numbers[j];    }}

参考

转载地址：http://fkxgi.baihongyu.com/