leetcode 268. 丢失的数字（Java版）

题目

https://leetcode-cn.com/problems/missing-number/

---

题解

解法 1

本题要求线性时间复杂度、仅使用额外常数空间的算法解决此问题，其实质是一个数学问题。

由于给定的数组本应包含从 0 到 n 范围内的所有数字，故可以将其看做一个首项为 0，尾项为length，步增为 1 的等差数列。

因此，求“缺项”的问题，可以转化为：先求等差数列前 n 项和，再减去已经存在的每一项 的问题。

本算法的时间复杂度为O(n)，空间复杂度为O(1)

package test;public class Solution {public int missingNumber(int[] nums) {int sum = (0 + nums.length) * (nums.length + 1) / 2; // 等差数列求和for (int i = 0; i < nums.length; i++) {sum -= nums[i];}return sum;} }

解法 2

好像和以前的一道题（只出现一次的数字）有异曲同工之处。看了大家的题解，异或操作（^）是一种很好的方式，不用考虑 sum 越界问题。

举个例子：

0 ^ 4 = 4 4 ^ 4 = 0

那么，就可以不用求和，直接使用异或运算^进行 抵消，剩下的数字就是缺失的了。

再举个例子：

1^1^2^2^3 = 3

代码：

int missingNumber(vector<int>& nums) {int res = nums.size();for (int i = 0; i < nums.size(); ++i){res ^= nums[i];res ^= i;}return res; }

总结

以上是生活随笔为你收集整理的leetcode 268. 丢失的数字（Java版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。