leetcode136-Single Number

本文最后更新于:2022年8月1日 凌晨

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

Solution

First of all, need to recognize follow things:

  • XOR

    XOR is a binary operation, it stands for “exclusive or”, that is to say the resulting bit evaluates to one if only exactly one of the bits is set.

    This is its function table:

    1
    2
    3
    4
    5
    6
    a | b | a ^ b
    --|---|------
    0 | 0 | 0
    0 | 1 | 1
    1 | 0 | 1
    1 | 1 | 0

    This operation is performed between every two corresponding bits of a number.

    Example: 7 ^ 10
    In binary: 0111 ^ 1010

    1
    2
    3
    4
      0111
    ^ 1010
    ======
    1101 = 13

    Properties: The operation is commutative, associative and self-inverse.

  • XOR rules

    • any number XOR to itself return 0
    • any number XOR to 0 return itself

python code:

1
2
3
4
5
6
class Solution:
def singleNumber(self, nums: List[int]) -> int:
single_number = 0
for num in nums:
single_number ^= num
return single_number

Golang code:

1
2
3
4
5
6
7
func singleNumber(nums []int) int {
s_num := 0
for _,num := range nums{
s_num ^= num
}
return s_num
}

leetcode136-Single Number
https://yance.wiki/leetcode136/
作者
Yance Huang
发布于
2020年6月6日
许可协议