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

简介: 题目: 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 Given a non-empty array of integers, every element appears twice except for one. Find that single one. 说明: 你的算法应该具有线性时间复杂度。

题目:

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

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?

示例 1:

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

示例 2:

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

解题思路:

  • 排序数组,如果某个数与前后两个数均不相等则该数只出现一次。
  • 哈希映射,key 为每个数的值,value 为每个数出现的频率。最后找到 value = 1 的数返回。
  • 异或运算,直接进行异或操作求值。不使用额外空间。

异或运算(XOR)解题是最优雅的解法,且不使用额外空间,其概念为:

  • 如果我们对 0 和二进制位做 XOR 运算,得到的仍然是这个二进制位

    • a XOR 0 = a
  • 如果我们对相同的二进制位做 XOR 运算,返回的结果是 0

    • a XOR a = 0
  • XOR 满足交换律和结合律

代码:

借助哈希表:

Java:

哈希映射频率(可用于字符串出现频率的计算)

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer count = map.get(num); //get() 方法获取元素不存在时返回null
            count = count == null ? 1 : ++count; //count为null 时证明元素不存在,则频率改为1,否则count频率+1
            map.put(num, count); //加入映射表
        }
        for (Integer num : map.keySet())
            if (map.get(num) == 1) return num; //返回频率为1的数
        return 0;
    }
}

Python:

1、借助 try...except...,只适用于该题中重复元素重复出现次数为偶数次。

class Solution(object):
    def singleNumber(self, nums):
        hash_map = {}
        for i in nums:
            try:
                hash_map.pop(i) # 尝试移除该数
            except:
                hash_map[i] = 1 # 移除失败证明字典内没有该值,则添加到字典
        return hash_map.popitem()[0] #最后字典中只剩下一个键值对,返回其键值

2、字典映射频率(可用于字符串出现频率的计算)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_map = {}
        for num in nums:
            hash_map.setdefault(num, 0)
            hash_map[num] += 1 # 每次出现频率加一
        for k, v in hash_map.items(): #二次遍历返回频率为1的数
            if v == 1:
                return k
        return 0

亦或运算(XOR):

其处理逻辑可以简单理解为:

输入: [2 , 3 , 2 , 4 , 3] ,  初始化 result = 0

result = 0  XOR  2  =  2
result = 2  XOR  3  =  [2 , 3]
result =  [2 , 3]  XOR  2  =  3
result = 3  XOR  4  =  [3 , 4]
result = [3 , 4]  XOR  3  =  4

返回 result = 4

异或运算是位操作中最基本运算之一,以上是为方便理解异或运算而简化抽象的逻辑,如果想进一步了解位操作可以参考Wiki百科。

高级程序设计语言异或运算表示符号一般是 ^

Java:

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

Python:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result = result ^ num
        return result
目录
相关文章
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
99 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
45 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 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解题|前端学算法
136 0
|
算法 PHP
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
力扣(LeetCode)算法题解:1365. 有多少小于当前数字的数字
139 0
|
算法 PHP
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
力扣(LeetCode)算法题解:1323. 6 和 9 组成的最大数字
135 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
94 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
97 0
LeetCode 313. Super Ugly Number