剑指offer第五十题。

题目描述

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

解题思路

比较好想的是用一个map来存储和判断。

但是吧这个问题确实是可以不用额外的O(n)的空间，不过理解上就会难一点，所以还是用map来解决吧。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean duplicate(int numbers[],int length,int [] duplication) {
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<length;i++){
        if(!map.containsKey(numbers[i])){
            map.put(numbers[i],1);
        }else{
            map.put(numbers[i],map.get(numbers[i])+1);
            duplication[0] = numbers[i];
            return true;
        }
    }
    return false;
}