缺失数字(268)

上一篇题目的难度可能对很多同学引起了不适，今天将回归一道比较简单的题目，大概耗时2-3分钟即可学习！


有兴趣回顾上一篇题目的：


只出现一次的数字Ⅱ(137)

01、题目示例

本题比较简单哈~尽可能多的给出解法吧！

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


示例 1:

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

示例 2:

  1. 输入: [9,6,4,2,3,5,7,0,1]
  2. 输出: 8

说明:


你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?


PS：建议大家停留个两分钟先想一想…直接拉下去看题解就没什么意思了。

02、题目分析

说高斯公式，估计大家听着懵逼，其实就是那个 1 2 3 … n = (1 n) * n / 2，即：

PNG


首先求出数组的和，然后再利用公式求出前n 1项之和，最终求差值，即为缺失的值！比如下面长度为4的数组，缺失4。

PNG

  • 2 + 3 + 1 + 5 = 11
  • (1 5) * 5 / 2=15

  • 15 - 11 = 4


根据分析完成题解：（翻一个CPP牌子吧）

  1. //CPP 
  2. class Solution { 
  3.     public:
  4.     int missingNumber(vector<int>& nums) {
  5.         int length=nums.size(); 
  6.         int result=(length + 1)*length/2;
  7.         for(int e:nums) 
  8.             result-=e;
  9.         return result;
  10.     }
  11. };

时间复杂度O(N)，空间复杂度O(1)


执行结果：

PNG

03、位运算求解

位运算的方式，本质和数学法一样，都是通过与无序序列抵消，然后找到缺失值。所以不能说哪个更好，都掌握最好~


直接使用“异或”进行求解。这个其实讲了好多次了，就是利用“两个相同的数，使用异或可以相消除”的原理。


先给一个Go语言的示例：

  1. //Go
  2. func missingNumber(nums []int) int {
  3.     result := 0
  4.     for i,k := range nums {
  5.         result ^= k ^ i
  6.     }
  7.     return result ^ len(nums)
  8. }

再给一个Java的版本：

  1. //java
  2. class Solution {
  3.     public int missingNumber(int[] nums) {
  4.         int res = 0;
  5.         for(int i = 0; i < nums.length; i++ )
  6.             res ^= nums[i] ^ i;
  7.         return res ^ nums.length;
  8.     }
  9. }

为了照顾各语言大爷们的情绪，我还是会尽可能的多给出几种语言示例，但是，请记住：算法思想才是最重要的。


最后再补一个python的吧，毕竟这种语言，对于这种短短的题目，往往都可以弄出来一行代码求解的骚操作….

  1. #python
  2. class Solution:
  3.     def missingNumber(self, nums: List[int]) -> int:
  4.         return sum(range(len(nums) + 1)) - sum(nums)


所以，今天的问题你学会了吗？评论区留下你的想法！