LeetCode 268: Missing Number

Difficulty: Easy

Tags: Array, Math, Bit Manipulation

问题描述

给定一个包含 n 个独特整型数的数组 nums，这 n 个数是从 0, 1, 2, …, n 中取出的，找到数组中缺失的那个数字。

解决方案

XOR

将数组 nums 和 [0, 1, 2, …, n] 中所有元素异或一遍，数组 nums 中的数字会出现2遍，异或后为0，最后的结果就是我们要找的元素。

▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n;

        for(int i=0; i<n; i++)
        {
            res ^= nums[i];
            res ^= i;
        }

        return res;
    }
};

回到 Conquer Leetcode