两道“原地”哈希题

442. 数组中重复的数据

题目链接：442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

题解

由题目可知数组 nums 中的 n 个数都在 [1, n] 的范围内，因为是数字的个数和位置个数应该一一对应如果有数字出现了两次，就意味着 [1,n] 中有数字没有出现过。

解题突破口就是，将每一个数放在对应的位置。如果位置和值不相等，就是出现两次的数。

由于数组的下标范围是 [0, n-1]，我们需要将数 i 放在数组中下标为 i-1 的位置。如果 nums[i] 恰好出现了一次，那么将 nums[i] 放在数组中下标为 nums[i]−1 的位置即可； 如果 nums[i] 出现了两次，那么我们希望其中的一个 nums[i] 放在数组下标中为 nums[i]−1 的位置，另一个 nums[i] 放置在任意「不冲突」的位置 x。

代码实现

• 遍历数组；
  • 当遍历到位置 i 时，看 nums[i] 和 nums[i]−1，是否相同；
  • 如果相同这开始从下一个数字开始比较；
  • 如果不同则应该把 nums[i]−1 放在对应的位置上，因此我们交换 num[i] 和 nums[nums[i]−1] 即可，直到待交换的两个元素相等为止；
• 遍历数组，找到数组中下标和值不一样的数字就是 重复出现两次的数 加入到resul 中即可；
• 返回结果 result。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> result;
        /* 原地啊交换数组 */
        for(int i = 0; i < nums.size(); i++)
            while (nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        /* 找到数组中下标和值不一样的数字就是 重复出现两次的数 */
        for(int i = 0; i < nums.size(); ++i)
            if (nums[i] - 1 != i) result.emplace_back(nums[i]);
        return result;
    }
};

41. 缺失的第一个正数

题目链接：41. 缺失的第一个正数

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

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

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                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;
    }
};