剑指50-数组中重复的数字

哈希表、in-place方法、快慢指针

题目描述

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

解法

这个题目和之前有个题很像，数组除了两个数字，其余数字都是出现了两次

这两道题都能用万能解法，哈希表

这道题除了哈希表还有一种方法：in-place，也叫下标定位法

数组里每个数组都会指向下一个下标，当numbers[i] == numbers[numbers[i]]时，numbers[i]为重复的数字，在此之前，需要一直交换numbers[i]和numbers[numbers[i]]，直到i != numbers[i]，就是自己指向自己

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) {


     for (int i=0; i<length; ++i) {
         // 不相等就一直交换
         while (i != numbers[i]) {
             if (numbers[i] != numbers[numbers[i]]) {
                 swap(numbers[i], numbers[numbers[i]]);
             }
             else {
                 *duplication = numbers[i];
                 return true;
             }
         }

     }
     return false;
 }
};

顺便把哈希表的解法也带上

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) {
        map<int, int> res_map;
        for(int i=0;i<length;i++)
        {
            if(res_map[numbers[i]]!=0) 
            {
                *duplication = numbers[i];
                return true;
            }
            res_map[numbers[i]]++;
        }
        return false;
    }
};

总结

这道题我有想到一个方法，就是快慢指针，龟兔赛跑算法，但是我理解了这个算法的目的，快慢指针可以检测出数组是否存在环，但是，不能确定sings hi都存在重复的数字，因为形成环不一定需要重复数字，例如[2,1,3,0,5]，这里的2、1、0构成环，所以快慢指针会返回2，这里也罢错误的记录下

        int fast=numbers[0];
        int slow=numbers[0];
        while(true)
        {
            fast=numbers[numbers[fast]];
            slow=numbers[slow];
            if(fast==slow)
            {
                break;
            }
        }
        fast=numbers[0]; //充值快指针
        while(true)
        {
            fast=numbers[fast];
            slow=numbers[slow];
            if(fast=slow)
            {
                *duplication=fast;
                return true;
            }
        }

    }