268. Missing Number

文章目录

1. 1. 题目
2. 2. 思路

题目

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

思路

这道题真的非常简单，我想的方法是直接创建一个长度为sum+1的有序数组和它做差集，输出结果。

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result= set(range(len(nums)+1))
        result=result - set(nums)
        return a[0]

有点丑陋，但是能跑。

然后我看到一个比较巧妙的单行代码：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return (len(nums) * (len(nums) + 1) // 2) - sum(nums)

原理是求和做差，很简单的道理。n*(n+1)/2是0到n的和，减去数组里的所有数的和就能找到那个少掉的数。

---

还有个异或的算法，原理是a^b^b=a，相同的数字异或会消除自身，而且异或满足交换律结合律，所以最后就会变成：

a ^ b ^ a ^ b ^ c ^ c ^ d
= ( a ^ a ) ^ ( b ^ b ) ^ ( c ^ c ) ^ d
= 0 ^ 0 ^ 0 ^ d
= d

代码如下：

public int missingNumber(int[] nums) {

    int xor = 0, i = 0;
	for (i = 0; i < nums.length; i++) {
		xor = xor ^ i ^ nums[i];
	}

	return xor ^ i;
}