268.缺失数字

第268题：给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

缺失数字.jpg

  1. 高斯公式求解
    \sum_{i=0}^{n}i=\frac{n(n + 1)}{2}
    首先求出数组的和，然后再利用公式求出前n+1项之和，最终求差值，即为缺失的。
 //CPP
 class Solution {
 public:
     int missingNumber(vector<int>& nums) {
         int length=nums.size();
         int result=(length+1)*length/2;
         for(int e:nums)
             result-=e;
         return result;
    }
};

2.位运算求解
利用“两个相同的数，使用异或可以相消除”的原理。

//Go
func missingNumber(nums []int) int {
    result := 0
    for i,k := range nums {
        result ^= k ^ i
    }
    return result ^ len(nums)
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容