【数据结构OJ题】消失的数字

原题链接：https://leetcode.cn/problems/missing-number-lcci/

目录

1. 题目描述

2. 思路分析

3.代码实现

---

1. 题目描述

2. 思路分析

方法一：排序+遍历（下一个数不等于上一个数+1，这个下一个数就是消失的数字）。

时间复杂度：O(N*logN） （这里用比较快的qsort排序）

方法二：0+1+2...+(n-1)+n用等差数列求和公式计算，求和结果依次减去数组中的值，最后的结果就是消失的数字。

时间复杂度：O(N)

方法三：单身狗思路，异或。

时间复杂度：O(N)

不了解单身狗问题的小伙伴可以看看这篇文章：https://blog.csdn.net/m0_62531913/article/details/132053191?spm=1001.2014.3001.5501

3.代码实现

因为第一种方法的时间复杂度比较高，这里就不写出来了。

方法二：

int missingNumber(int* nums, int numsSize){int n=numsSize;int s=(0+n)*(n+1)/2;for(int i=0;i<n;i++){s-=nums[i];}return s;
}

 方法三：

int missingNumber(int* nums, int numsSize){int n=numsSize;int ret=0;for(int i=0;i<=n;i++){ret^=i;}for(int i=0;i<n;i++){ret^=nums[i];}return ret;
}