手撕C语言题典——消失的数字

本文主要是介绍手撕C语言题典——消失的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

前言

一，思路

1)排序查找

2）数据求和，依次减去中值

3） 异或

二，异或的代码实现

---

前言

    依旧是一道力扣上的题，通过不同思路的不同时间复杂度来分析，让我们看看有什么不同。

面试题 17.04. 消失的数字 - 力扣（LeetCode）https://leetcode.cn/problems/missing-number-lcci/description/

     题目很简单，我们先不考虑题目要求的时间复杂度，单纯从思路来看，然后再计算相对应的时间复杂度 。

一，思路

1)排序查找

最简单的也是最容易想出来的思路：

      我们只需要对数据进行排序，再依次遍历，如果发现下一个数不是上一个数据+1，则这个数就是消失的数。

2）数据求和，依次减去中值

贴一下笔记：

3） 异或

        异或只需要知道 相同的值异或之后是零，比如 1^1 = 0，后面会出一期详细讲一下异或的性质和应用。

二，异或的代码实现

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

因为只有简单的循环且并没有嵌套，同样异或的时间复杂度也是O(N)

这篇关于手撕C语言题典——消失的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---