美文网首页Leetcode
Leetcode.268.Missing Number

Leetcode.268.Missing Number

作者: Jimmy木 | 来源:发表于2019-12-10 09:40 被阅读0次

    题目

    给定一个数组,里面数字是从0到n,但是缺了一个数,找出缺的数字。

    Input:[3,0,1]
    Output: 2
    Input:[9,6,4,2,3,5,7,0,1]
    Output: 8
    Input:[0]
    Output: 1
    Input:[1]
    Output: 0
    

    思路1

    使用n+1的数组做标记,有这个数就标记为1,没有就标记为0。最后找出为0的数。

    int missingNumber1(vector<int>& nums) {
        vector<int> vec(nums.size()+1,0);
    
        for (int a : nums) {
            vec[a] = 1;
        }
    
        for (int i = 0;i < vec.size();i++) {
            if (vec[i] == 0) {
                return i;
            }
        }
    
        return (int)nums.size();
    }
    

    思路2

    位运算,异或运算。分别对前n个数做异或,对给定数做异或,然后对两者再做异或,即可找到缺失的数。

      int missingNumber(vector<int>& nums)
      {
          if (nums.empty()) return 0;
          int all = 0x0;
          int cur = 0x0;
          for (int i = 0; i < nums.size()+1; i++) {
              all = all ^ i;
              if (i != nums.size()) {
                  cur = cur ^ nums[i];
              }
          }
          return (all ^ cur);
      }
    

    总结

    神奇的异或操作,进行两次异或,负负得正的原理。

    相关文章

      网友评论

        本文标题:Leetcode.268.Missing Number

        本文链接:https://www.haomeiwen.com/subject/rnuwgctx.html