面试题 17.19. 消失的两个数字（On)

面试题 17.19. 消失的两个数字

• 这道理难点在于O(n)时间复杂度，O1的空间复杂度，我们可以在nums数组的对应位置的元素上加上30000，当更新元素时该位置的nums元素值大于了30000，那么说明前面有个元素的值为现在的元素位置的下标，我们只要 $$ nums[nums[i]-30000]+=30000 $$ 即可。比如：一开始$$ nums[4]=6,nums[6]=8,nums[8]=10 $$ 这时候i=4的时候，我们更新$$ nums[6]=8+30000=30008 $$ 遍历到i=6时，此时$$ nums[30008-30000]=nums[8]=10+30000=30010... $$以此类推，最后遍历发现小于30000的下标就是的。前后变化的情况和对应坐标如下：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int zhi=0;
        int sum=(nums.size()+2)*(nums.size()+3)>>1;
        // cout<<"sum="<<sum<<endl;
        for(int i=1;i<=nums.size()+2;i++)
        {
            zhi^=i;
        }
        int zhi2=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[]
            zhi2^=nums[i];
        }
        cout<<"zhi="<<zhi<<" zhi2="<<zhi2<<endl;
        cout<<"hh="<<(9^4)<<endl;
        int _1=0,_2=0;
        for(int i=1;i<=nums.size()+2;i++)
        {
            int aa=zhi^zhi2;//两个数
             cout<<"aa="<<aa;
             _1=aa^i;//剩下来的那个；
             cout<<"  _1="<<(_1);
             cout<<"sum="<<sum<<endl;
             cout<<"sum-_1="<<sum-(_1)<<" nums[i]="<<i<<endl;
            if((_1)<=nums.size()+2&&sum-(_1)==i)
            {
                _2=i;
                break;
            }
        }
        return {_1,_2};
    }
};

面试题 17.19. 消失的两个数字（On)

原文：https://www.cnblogs.com/Vampire6/p/13226381.html