leetcode_力扣_面试题 17.19. 消失的两个数字

题目描述

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例

• 示例 1

输入: [1]
输出: [2,3]

• 示例 2

输入: [2,3]
输出: [1,4]

提示

• nums.length <= 30000

解题思路

• 在原数组后新开辟两个位置，赋一个自定义的万能值 flag_blank;
• 遍历数组，使 i 下标位置的值必须为 i+1 或 我们定义的 flag_blank (原地交换的思路)；
• 再次遍历数组，记录下值为 flag_blank 的下标 i，将 i+1 加入到要返回的容器中。

代码

class Solution {
public:

    int flag_blank = 30001;
    void my_swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
    }

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

        nums.push_back(flag_blank);
        nums.push_back(flag_blank);

        int nums_len = nums.size();
        vector<int> ret;

        int i;

        for(i = 0; i < nums_len; i++){

            if(nums[i] == i+1){
                continue;
            }
            while(nums[i] != flag_blank && nums[i] != i+1){

                my_swap(nums[i], nums[nums[i]-1]);

            }

        }

        for(i = 0; i < nums_len; i++){
            if(nums[i] == flag_blank){
                ret.push_back(i+1);
            }
        }

        

        return ret;
    }
};

提交结果

总结

• 原地交换法。