Try   HackMD

【LeetCode】 268. Missing Number

Description

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

給予一個陣列 nums 它包含 n 個不同的數字且都落在 [0, n] 之中,回傳範圍內唯一一個不在陣列中的數字。

Example:

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.


Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.


Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Solution

  • 題目的 Follow up 中有提到,是否能提出一個答案使用 O(1) 的額外空間複雜度和 O(n) 的時間複雜度。
    • 既然時間複雜度在 O(n),答案就必定不需要排序。
  • 我的想法是利用 A XOR A = 0 這點,把 0 ~ n 都 XOR 起來之後,再與陣列中每個數 XOR。
    • 同樣的數字互相 XOR 都會不見,留下的數字即為答案。

Code

class Solution { public: int missingNumber(vector<int>& nums) { int temp = 0; for(int i = 0; i < nums.size(); i++) { temp ^= nums[i]; temp ^= i; } return temp ^= nums.size(); } };
tags: LeetCode C++