WildPointer

Welcome to my world!


  • Arc

  • Cat

  • Tag

  • Proj

  • Tech

  • Donate

  • Me

  • Search

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

Shengjia Yan

Shengjia Yan

职业码农 业余作家

29 posts
11 categories
42 tags
GitHub Linkedin Zhihu Weibo Twitter Instagram Bilibili YouTube Twitch
Creative Commons
Links
  • LeetCode
  • 小土刀
  • 52nlp
© 2016 - 2021 Shengjia Yan
追随我心