LeetCode Single Number

Problem

Given an 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?

一个整型数组，除一个元素外，其余的元素都出现两次，要求不用额外内存，线性时间内找到这个元素

Python 实现

# Given an 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?
# author li.hzh

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


print(Solution().singleNumber([1, 1, 4, 4, 3, 5, 3, 6, 6]))

分析

题目要去不开额外内存，线性时间，显然需要特殊 运算的支持。这里位运算中的异或运算恰好满足 A ^ B ^ A = B 的规律，符合题意。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号