原地哈希/LeetCode [41/442/448]

這種原地雜湊演算法适用于和正整數有關，且數字範圍和數組長度有關的題目裡，映射之後能利用映射關系（下标和值一一對應）來找到解。

1.題目連結：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/

• 由于不能使用額外空間，哈希表等其他資料結構就無法使用了。
• 我們采取一種特殊的原地哈希：

  f(nums[i]) = num[i] - 1

  ,也就是将值為nums[i]的數字映射到nums[i]-1的下标位置，例：3映射到數組下标為2。
• 算法過程：
• 1.周遊數組，然後采取原地哈希，将現在位置上的數和映射過後下标(idx)上的數交換，循環直到

  nums[nums[i] - 1] != nums[i]

  （也就是idx上的數和目前的數一樣了）。
• 2.最後再周遊一下這個調整過的數組，發現值和下标不對應的話，說明和這個下标對應的值沒有出現過了。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        auto ans = vector<int>{};

        //f(nums[i]) = nums[i] - 1
        for(int i = 0; i < n; ++i){
            while(nums[nums[i] - 1] != nums[i]){
                int idx = nums[i] - 1;
                int t = nums[idx];
                nums[idx] = nums[i];
                nums[i] = t;
            }
        }

        for(int i = 0; i < n; ++i){
            if(nums[i] - 1 != i) ans.push_back(i + 1);
        }

        return ans;
    }
};
           

2.https://leetcode-cn.com/problems/first-missing-positive/

• 思路和上題差不多也是采用原地哈希。
• 将小于n且大于0的值映射到相關位置上（

  index = nums[i] - 1

  ），這樣重新周遊的時候，第一個和下标不對應的就是第一個沒出現過的最小的正整數。
• 這裡映射的時候要減1，不能2映射到下标2，不然的話下标0放什麼數就不懂了。

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;
                // 将nums[i] 放置到對應位置上[1,2,3...]
                int idx = nums[i] - 1;
                nums[i] = nums[idx];
                nums[idx] = idx + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != (i + 1)) {
                return (i + 1);
            }
        }
        return (n + 1);
    }
};
           

3.https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/

• 同樣原地哈希。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n = nums.size();
        auto ans = vector<int>{};

        for(int i = 0; i < n; ++i){
            while(nums[nums[i] - 1] != nums[i]){
                int idx = nums[i] - 1;

                int t = nums[idx];
                nums[idx] = nums[i];
                nums[i] = t; 
            }
        }
        
        for(int i = 0; i < n; ++i){
            if(i != nums[i] - 1) ans.push_back(nums[i]);
        }
        return ans;

        // unordered_set<int> hash_set;
        // for(auto num : nums){
        //     if(hash_set.count(num)) ans.push_back(num);
        //     else hash_set.insert(num);
        // }

        // return ans;
    }
};