LeetCode 136: Single Number

Difficulty: Easy

Tags: Hash Table, Bit Manipulation

问题描述

一个数组，除了一个数字出现一次外其他都出现了两次，找到这个数字。

解决方案

这题可以用按位异或这个技巧很快解决。

因为 A^A = 0，将这个数组里的数字依次按位异或，所有重复出现的数字都会被消去，最后得到的结果就是我们要找的那个数字。

▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

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

回到 Conquer Leetcode