[LeetCode] 136. Single Number 单独数

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 136. Single Number 单独数,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

Note:java

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

Example 1:数组

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

Example 2:app

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

因为要求时间复杂度O(n),空间复杂度O(1),因此不能用排序法,也不能使用map。post

解法1:用两倍全部非重复元素和减去原数组。url

解法2:位操做Bit Operation,使用二进制数位操做中的异或,同为0,异为1。主要考察位操做。spa

异或运算{\displaystyle A\oplus B}A\oplus B的真值表以下: F表示false,T表示true htm

 
A B
F F F
F T T
T F T
T T F

 

Java:blog

public class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
}

Python:

def singleNumber(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    return 2 * sum(set(nums)) - sum(nums)  

Python:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for num in nums:
            res ^= num
            
        return res  

Python:

import operator
from functools import reduce

class Solution:
    """
    :type nums: List[int]
    :rtype: int
    """
    def singleNumber(self, A):
        return reduce(operator.xor, A)  

C++:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto num : nums) res ^= num;
        return res;
    }
};

 

相似题目:

[LeetCode] 137. Single Number II 单独数 II

[LeetCode] 260. Single Number III 单独数 III

 

All LeetCode Questions List 题目汇总