【LeetCode】136. Single Number 解題報告

撰寫於2021-08-22閱讀次數

136. Single Number / Easy

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

Solution

思路

這題有很多有趣的解法，但題目要求空間複雜度必須是O(1)，時間複雜度是O(N)，這就限制了這題的解法。要判斷是否出現過，可能需要 set、map 或至少 array，不使用額外的空間真的很困難。

有一個有趣的解法是利用 xor 的特性，同樣的數 xor 後會變成 0。題目已經提到，只有一個元素出現一次，其他都有兩次，如此一來，我們遍歷整個陣列，將所有的數字 xor 起來，最後留下來的就是答案了。

效能

Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(1)

LeetCode Result

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int n = nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            n ^= nums[i];
        }
        return n;
    }
};