leetcode 剑指 Offer 03. 数组中重复的数字

leetcode

1. Map
   C++：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {

        std::map<int, int> numberIndexMap;
        for ( int i = 0; i < nums.size(); ++i ) {

            if ( numberIndexMap.find(nums[i]) != numberIndexMap.end() ) {

                return nums[i];
            }

            numberIndexMap[nums[i]] = i;
        }

        return 0;
    }
};

2. 原地哈希法
   C++：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {

        for ( int i = 0; i < nums.size(); ++i ) {
            
            while ( nums[i] != i ) {
                
                if ( nums[i] == nums[nums[i]] ) {

                    return nums[i];
                }

                while (nums[i] != nums[nums[i]]) {

                    std::swap(nums[i], nums[nums[i]]);
                }
            }
        }

        return 0;
    }
};