leetcode-268. 缺失数字，难度：简单leetcode-136. 只出现一次的数字，难度：简单-阿南达文事网

leetcode-268. 缺失数字，难度：简单 leetcode-136. 只出现一次的数字，难度：简单

268 题目

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

示例 1:
输入: [3,0,1]
输出: 2

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

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

思路

因为数组中必有一数缺失，那么我们可以先找出数组中的最大值（用于界定完整序列的范围），再分别求出完整序列和与数组数字和，相减即得缺失数字。

代码

class Solution {public int missingNumber(int[] nums) {//特殊情况if (nums.length == 1) {if (nums[0] == 0) {return 1;}else if (nums[0] == 1) {return 0;}}int max = nums[0];int sumMiss = 0;int sum = 0;int result;//找出数组中最大值并求和for (int i = 0; i < nums.length; i++) {if (nums[i] > max) {max = nums[i];}sumMiss += nums[i];}//求出原始序列和for (int i = 0; i <= max; i++) {sum += i;}result = sum - sumMiss;//注意特殊情况if (result == 0 && max == nums.length - 1) {result = max + 1;}return result;}
}

结果

联想

做完后看评论区有大佬用位运算 -> 这里
忽然想起以前做过的一道题…

136 题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

思路

异或（^）运算满足：

交换律：a ^ b ^ c <=> a ^ c ^ b
任何数于0异或为任何数 0 ^ n => n
相同的数异或为0: n ^ n => 0

知道这些性质后，那么我们只要让数组元素一直异或运算下去便可得到出现一次的数字了。

代码

class Solution {public int singleNumber(int[] nums) {int result = 0;for (int i = 0; i < nums.length; i++) {result ^= nums[i];}return result;}
}

复盘

思路

回到268题，同样的，我们可以让原始序列和数组元素进行异或运算。虽然我们求的是缺失的数，但这样运算从某种意义上我们同样能够得到原始序列相较于数组多出的数。
例如：
a = [2,3,1,6,4,0]
2 ^ 0 ^ 3 ^ 1 ^ 1 ^ 2 ^ 6 ^ 3 ^ 4 ^ 4 ^ 0 ^ 5 ^ 6 =>
0 ^ 0 ^ 1 ^ 1 ^ 2 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 ^ 5 ^ 6 ^ 6 =>
5

代码

class Solution {public int missingNumber(int[] nums) {int res = nums.length;for (int i = 0; i < nums.length; i++) {res ^= nums[i];res ^= i;}return res;}
}

结果

虽然思路和代码简单不少，但是内存消耗高了些。

leetcode-268. 缺失数字，难度：简单leetcode-136. 只出现一次的数字，难度：简单