时间复杂度的降低

原地哈希映射

问题的引入

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

找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

限制：2 <= n <= 100000

普通哈希（费空间）：

class Solution {
public:
    int num[100001] = {0};//需要提前预知所需内存

    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0; i<nums.size(); i++)
        {
            if(num[nums[i]] == 1) return nums[i];
            num[nums[i]]++;
        }
        return 0;
    }
};

原地哈希（空间复杂度：１）

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i<n; i++)
        {
            while(nums[i] != i)
            {
                if(nums[i] == nums[nums[i]]) break;//如果对应数字已经在原位上
                swap(nums[i], nums[nums[i]]);
            }
        }

        for(int i = 0; i<n; i++)
        {
            if(nums[i] != i)
                return nums[i];
        }
        return 0;
    }
};

原地哈希的应用

力扣41.缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

示例 2：

输入：nums = [3,4,-1,1]
输出：2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

由于数值范围太大，普通哈希无法满足。所以应该采用第二种方法，原地哈希。

优质方法：原地哈希

把数组视为哈希表，对数字进行原地交换。而缺失的数字一定在 [1, N+1] 的范围里面，我们可以把原数组作为哈希表来使用。

确定映射法则：hash[num] = num+1;

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i<n; i++)
        {
            while(nums[i] != i+1)
            {
                //当　当前位置的数值超出范围　或　当前的数值应该在原来的位置上，则
                if(nums[i] <= 0 || nums[i] > n || nums[i] == nums[nums[i]-1]) 
                    break;
                //如果目前所在位置对应的数值在１～N范围内，且未对应当前位置
                swap(nums[i], nums[nums[i]-1]);//则交换
            }
        }

        for(int i = 0; i<n; i++)
        {
            if(nums[i] != i+1) //未配对成功的第一个位置
                return i+1;
        }
        return n+1;//如果全部配对成功，则说明前N项的值都在，说明最小缺失的数字为 N+1 
    }
};