寻找"单身数"

一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1)

异或运算

  • 两个相同的数进行异或运算, 结果为0 5^5 == 0
  • 0 与非零数进行异或运算, 结果为非零数本身 0^10 == 10
  • 异或运算符合交换律10^20^30^40 == 20^30^10^40

解题思路:

代码实现:

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

def main():
    so = Solution()
    result = so.singleNumber([10, 20, 50, 80, 10, 50, 80, 5,  20])
    print("单身数为:", result)

if __name__ == '__main__':
    main()

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

不用加号实现两整数相加

对于二进制的加法运算,若不考虑进位,则1+1=0,1+0=1,0+1=1,0+0=0,通过对比异或,不难发现,此方法与异或运算类似。因而排出进位,加法可用异或来...

592
来自专栏程序生活

求一个数n次方后的末尾数(数论/快速幂)问题描述解题思路代码实现运行结果参考

问题描述 hdu1061-Rightmost Digit hdu1097-A hard puzzle 这两个oj题目思路几乎一样,都是为了快速求出一个数n次...

4687
来自专栏数据结构与算法

177. [USACO Jan07] 有限制的素数

177. [USACO Jan07] ★   输入文件:qprime.in   输出文件:qprime.out   简单对比 时间限制:1 s   内存限制:...

3649
来自专栏WD学习记录

牛客网 二进制中1的个数

892
来自专栏程序生活

Leetcode-Easy 461.Hamming Distance

Leetcode-Easy是Leecode难度为"Easy"的解法,由python编码实现。 461.Hamming Distance 描述: ? 思路: 首...

2825
来自专栏机器学习实践二三事

leetcode之-题17

题目 Given a digit string, return all possible letter combinations that the numbe...

1958
来自专栏韦弦的偶尔分享

Swift 计数质数 - LeetCode

1993
来自专栏java学习

面试题42(在JAVA中,下列哪些是Object类的方法)

在JAVA中,下列哪些是Object类的方法? ---- A synchronized() B wait() C notify() D notifyAll()...

4566
来自专栏小筱月

javascript sort 函数用法

简单的说,sort() 在没有参数时,返回的结果是按升序来排列的。即字符串的Unicode码位点(code point)排序

1523
来自专栏swag code

swap()交换两个变量的方法汇总

1014

扫码关注云+社区

领取腾讯云代金券