【剑指offer】问题3：数组中重复的数字

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

先上代码

    /**
     * 第一题：长度为n的数字中，存放着0-n-1范围的数字，如果有重复数字，任意找出一个即可。
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        boolean ret = false;
        if(numbers == null)
            return ret;
        if(length == 0)
            return ret;
        int i = 0;
        while(i < numbers.length){
            int target = numbers[i];
            if(i == target){
                i++;
            }else{
                if(numbers[target] == target){
                    ret = true;
                    duplication[0] = target;
                    return ret;
                }else{
                    int tmp = numbers[target];
                    numbers[target] = target;
                    numbers[i] = tmp;
                }
            }
        }
        return ret;
    }

这个题细细品味还是很好的。拿到这个题目，最不费脑子的做法就是创建一个辅助map，key值就是0~n-1 数字的值，value值可以是他们出现的次数。这样可以完成题目要求。但是这样时间时间复杂度是O(n)，空间复杂度也是O(n)。要相信题干之中无废话。如果借助辅助空间，其实数组内数字是什么值就无关紧要了，0~n-1 这个条件我们也就用不上了。细想，大小为n的数组，然后数组内容的取值恰巧又在0~n-1 这个范围内，跟数组索引值完全一致，利用这两点，就可以搞点事情了。这就引出了以上这种解法的核心思想：将数值放到与其相等的数组索引位置上，放之前判断此位置上的值是否已经和索引值相等，如果相等那么即可返回该值。顺着这思路，不难写出上面的代码。分析下算法复杂度：该实现没有借助额外的存储空间；每个数字，最多经过两次交换即可到达他应该在的位置（其实最多就是一次被动被换走，然后轮到他判断时又主动被换走，这两次操作），因此时间复杂度是O(n)。

总结：

1. 对题干一定要认真揣摩，一定没有多余的废话；
2. 充分利用题目中数据结构自身的特点，结合存储内容的数据特点，发觉二者之间的关系。