LeetCode 136. 只出现一次的数字 Single Number

简介: LeetCode 136. 只出现一次的数字 Single Number

LeetCode 136. 只出现一次的数字 Single Number


Table of Contents

中文版:

英文版:

My answer:

解题报告:

中文版:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

英文版:

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:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

My answer:

# version 1:时间复杂度为 O(n),由于使用 dictionary 记录每个元素出现次数,所以空间复杂度为 O(n)
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num_dict = {}
        for num in nums:
            if num in num_dict:
                num_dict[num] += 1
            else:
                num_dict[num] = 1
        for key in num_dict:
            if num_dict[key] == 1:
                return key
# version 2: 巧妙使用异或。异或的特性是:相同为0,不同为1;0 和 任意数 x 异或结果都是任意数 x 本身。
# 此方法不占用额外空间,且时间复杂度为 O(n)
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = res ^ num # 异或
        return res

解题报告:

如代码注释中解释。

两种方法:

1、既然提到了个数自然想到统计每个数字出现的次数,此方法不限于题目中提到的一次和两次。而第二种方法巧妙利用了这个特点。

2、异或,跟数字出现的奇数次和偶数次有关,因为一个数出现偶数次,异或的结果为0,跟没出现一样。

相关文章
|
6月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
66 1
|
11天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
8 0
|
6月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
22 0
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
|
存储 前端开发 算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
LeetCode只出现一次的数字使用JavaScript解题|前端学算法
112 0
|
算法 PHP
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
111 0
|
算法 PHP
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
107 0
|
算法 PHP
力扣(LeetCode)算法题解:1295. 统计位数为偶数的数字
力扣(LeetCode)算法题解:1295. 统计位数为偶数的数字
89 0
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode Contest 178-1365. 有多少小于当前数字的数字 How Many Numbers Are Smaller Than the Current Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates