导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一:加和
    2. 方法二:异或

LeetCode-268.Missing Number

题目

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

翻译

给出一个包含从0到n中n个不同数字的数组,找到数组中缺失的数字。
例如,给出nums = [0, 1, 3],返回2。
注意:你的算法应当运行在线性时间复杂度内。你能只用常数额外空间复杂度实现吗?

方法一:加和

如果不缺数字的话,则从0到n所有数和为 sum = n * (n + 1) / 2;求出nums中所有数的和numsSum,则sum - numsSum即为所求:

1
2
3
4
5
6
7
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length, sum = n * (n + 1) / 2, numsSum = 0;
for (int i = 0; i < nums.length; i++) numsSum += nums[i];
return sum - numsSum;
}
}

方法二:异或

异或相对于求和和乘积等运算,有不会导致溢出的优点:

1
2
3
4
5
6
7
8
public class Solution {
public int missingNumber(int[] nums) {
int n = nums.length, xor = 0, numsXor = nums[0];
for (int i = 1; i < n + 1; i++) xor ^= i;
for (int i = 1; i < nums.length; i++) numsXor ^= nums[i];
return xor ^ numsXor;
}
}

参考:
http://www.geeksforgeeks.org/find-the-missing-number/