268. Missing Number

發表於 | 分類於

problem

給定一維陣列，那一個數字遺失

solution

math

三角形公式

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n*(n+1)/2;
        for(int n:nums) total-=n;
        return total;
        
    }
};
  • total變數，可能會有overflow 問題

Bit

  • 善用 x^x=0 以及 XOR交換率
  • 因題目限制，陣列元素只會是正整數，利用陣列索引與元素做XOR
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size(), ret = n;
        for(int i=0;i<n; ++i) ret^= (i^nums[i]);
        return ret;
        
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)