剑指offer3: 数组重复数字

题目描述：在一个长度为n的数组里的所有数字都在0～n-1之间。数组中某些数字时重复的，但不知道有几个重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

---

思路一：哈希表法

使用一个长度为n的哈希s数组记录每个数字出现的次数。一边遍历数组一边查询哈希表，遍历一遍，时间复杂度为o(n),空间复杂度也为o(n).

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        if(length==0){
            return false;
        }
        if(length==1){
            return true;
        }
        vector<int> temp(length, -1);
        for(int i=0; i < length; i++){
            int value = numbers[i];
            if(temp[value]== -1){
                temp[value]++;}
            else{
                *duplication = value;
                return true;}
        }
    return false;
    }
};

---

思路二：

由于数组数字都在0～n-1之间，如果没有重复数字，那么每个数字排序后应该和数组index相等。从头扫描数组，当扫描到下标为i的数字m时。比较数字m和i时候相等，是则扫描下一个；不是，则比较m和下标为m的数字，相等则为重复数字，不等则交换，重复。

class Solution {
public:
    bool duplicate(int numbers[], int length, int* duplication) {
        if(length==0){
            return false;
        }
        if(length==1){
            return true;
        }
        for(int i=0;i < length; i++){
            int m=numbers[i];
            if(m==i){
                continue;
            }
            else{
                int tmp = numbers[m];
                if(m==tmp){
                    *duplication = m;
                    return true;
                }
                else{
                    numbers[m]=m;
                    numbers[i]=tmp;
                }
            }
        }
    return false;
    }
};

若要找出所有重复数字，返回list；若要返回每个重复数字以及重复次数，返回map.