原地标记/交换

一、原地标记

题干：题目限制空间复杂度
思路：
step1：想出空间o(n)map方法
step2：以原数组下标做o(n)map方法的key，想办法在数据上做手脚
step3：再遍历时，检查数据是否被做了手脚

• 448. 找到所有数组中消失的数字

class Solution {

public:

    vector<int> findDisappearedNumbers(vector<int>& nums) {

        vector<int> res;

        int size=nums.size();

        for(auto num:nums){

            int temp = (num - 1) % size;

            nums[temp] += size;

        }

        for(int i=0;i<size;i++){

            if(nums[i]<=size){

                res.push_back(i+1);

            }

        }

        return res;

    }

};

• 442. 数组中重复的数据

class Solution {

public:

    vector<int> findDuplicates(vector<int>& nums) {

        vector<int> res;

        int size=nums.size();

        // if(size<2) return res;

        for(auto num:nums){

            int temp=(num-1)%size;

            nums[temp]+=size;

        }

        for(int i=0;i<size;i++){

            if(nums[i]>size*2){

                res.push_back(i+1);

            }

        }

        return res;

    }

};

二、原地交换

题干：限制空间复杂度，且正好数据与数组下标有关系
思路：
step1：找到数据与数组下标的关系
step2：遍历数组，将 满足条件的数据 与 对应数组下标原位置数据交换，即遍历完成应达到效果——每个满足条件的数据都交换到了对应的下标位置。
step3：遍历数组，找到某个下标未配对的组合

• 41. 缺失的第一个正数

class Solution {

public:

    int firstMissingPositive(vector<int>& nums) {

        int size=nums.size();

        for(int i=0;i<size;){

            if(nums[i]>0&&nums[i]<=size){

                int temp=nums[i];

                if(nums[temp-1]==temp){

                    ++i;

                }else{

                    nums[i]=nums[temp-1];

                    nums[temp-1]=temp;

                }

            }else{

                ++i;

            }

        }

        int res=0;

        for(;res<size&&nums[res]==res+1;res++);

        return res+1;

    }

};