ORIGIN

LeetCode_Single-Number

ACM 1 mins190 words

Problem Description

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

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

Example 2:

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

Analysis

This is just a simple bit XOR Operation but its not easy to think of.

There are three rules of XOR.

  1. The integer XOR with itself will get 0. Because the computer will first change your number in ten to number in two, then XOR each digits of the two numbers. So, 35 XOR 35 is 0.
  2. 0 XOR a (an integer) will get a.
  3. XOR satisfies Commutative law. (3 ^ 5 ^ 3 ^ 5 = 3 ^ 3 ^ 5 ^ 5)

So, we just need to XOR all the numbers and each number appears twice except one. The one will be left.

Code

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(int i = 0; i < nums.size(); i ++) {
ans = ans ^ nums[i];
}
return ans;
}
};
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|