【LintCode 简单】82. 落单的数

深碍√TFBOYSˉ_ 2022-06-01 00:54 143阅读 0赞

1.问题描述：

给出2\*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

2.样例：

给出 \[1,2,2,1,3,4,3\]，返回 4

[挑战 ][Link 1]

一次遍历，常数级的额外空间复杂度

3.代码：

class Solution:
        """
        @param: A: An integer array
        @return: An integer
        """
        """
        def singleNumber(self, A):
            # write your code here
            length = len(A)
            for i in range(length):
                fg=True
                for j in range(length):
                    if A[i]==A[j] and i!=j:
                        fg=False
                        break
                if fg:        
                    return A[i]
        """
        #异或运算
        def singleNumber(self, A):
            # write your code here
            length = len(A)
            ans=0
            for i in range(length):
                ans^=A[i]
            return ans

异或运算： 1^0=1  0^1 = 1 0^0= 0 1^1=0  
相同的数做异或运算等于0 不相等等于1，通过异或运算找出那个单独的数。思想比较巧妙，复杂度相对于循环两次，大大降低。

[Link 1]: http://www.lintcode.com/zh-cn/problem/single-number/#challenge

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode 391. 数飞机

给出飞机的起飞和降落时间的列表，用序列 interval 表示. 请计算出天上同时最多有多少架飞机？样例样例 1: 输入: [(1, 1

亦凉/ 2023年07月06日 06:17/ 0 赞/ 9 阅读

相关【LintCode 简单】326. 滑动数独

1. 描述给定一个3×n3×n 的矩阵 `number`，并且该矩阵只含有1到9的正整数。考虑有一个大小为 3×33×3 滑动窗口，从左到右遍历该矩阵 `number

旧城等待，/ 2023年01月17日 07:42/ 0 赞/ 118 阅读

相关【LintCode 简单】838. 子数组和为K

1. 问题描述给定一个整数数组和一个整数k，你需要找到连续子数列的和为k的总个数。 2. 样例样例1 输入: nums = [1,1,1] 和 k =

╰+攻爆jí腚メ/ 2022年10月23日 15:24/ 0 赞/ 154 阅读

相关【日常学习】【二进制】codevs3295 落单的数题解

版权信息转载请注明出处 \[[ametake][]版权所有\][http://blog.csdn.net/ametake][ametake]欢迎来看看题目来源：九章算法面

待我称王封你为后i/ 2022年08月02日 00:09/ 0 赞/ 404 阅读

相关 lintcode491.回文数

lintcode491.回文数判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。注意事项给的数一定保证是32位正整数

本是古典何须时尚/ 2022年06月10日 23:54/ 0 赞/ 142 阅读

相关【LintCode 简单】777. 完全平方数

1.问题描述：给出一个正整数 `num`,写一个函数，要求当这个当`num`为完全平方数时函数返回`True`，否则返回`False` 注意事项 `不要`用诸如sqr

骑猪看日落/ 2022年06月01日 11:44/ 0 赞/ 179 阅读

相关【LintCode 简单】488. 快乐数

1.问题描述：写一个算法来判断一个数是不是"快乐数"。一个数是不是快乐是这么定义的：对于一个正整数，每一次将该数替换为他每个位置上的数字的平方和，然后重复这个过程直到

今天药忘吃喽~/ 2022年06月01日 07:55/ 0 赞/ 247 阅读

相关【LintCode 简单】517. 丑数

1.问题描述：写一个程序来检测一个整数是不是`丑数`。丑数的定义是，只包含质因子 `2, 3, 5` 的正整数。比如 6, 8 就是丑数，但是 14 不是丑数以为

￡神魔★判官ぃ/ 2022年06月01日 05:50/ 0 赞/ 227 阅读

相关【LintCode 简单】491. 回文数

1.问题描述：判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。 2.样例： `11`, `121`, `1`, `

快来打我*/ 2022年06月01日 05:30/ 0 赞/ 155 阅读

相关【LintCode 简单】82. 落单的数

1.问题描述：给出2\n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。 2.样例：给出 \[1,2,2,1,3,4,3\]，返回

深碍√TFBOYSˉ_/ 2022年06月01日 00:54/ 0 赞/ 144 阅读