LeetCode 136:只出现一次的数字 Single Number
题目:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
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
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
前端 javascript 练习题 -简易年历及tab切换
前端 javascript 练习题 -简易年历及tab切换简易年历eg1:将数组中的值输出改变样式可以直接改样式,也可以修改类名var okuang=document.getElementById("kuang");var oli=document.getElementsByTagName("li");var arr=[11,22,33,44,55];var index=0; //定义一个变量用来保存索引值for(var i=0;i oli[i].onclick=function(){ for(var j=0;j<oli.length;j++){ //排他功能 oli[j].style.backgroundColor="#666"; oli[j].style.color="#fff"; } okuang.innerHTML=arr[index]; //此时不能用arr[i],因为在点击之前for已经执行完了,此时i为oli的元素个数值 this.style.backgroundColor="red"; this.style.color="#000"; index++; }} 解析...
- 下一篇
Spring-Boot-Api-Starter 基于Spring Boot快速构建项目的脚手架
简介 Spring-Boot-Api-Starter是一个基于SpringBoot,快速构建RESTful API工程的脚手架,支持多数据源配置、分布式事务;快速生成各模块的基础代码,极大的提升了开发效率,使团队代码风格保持统一。项目地址:https://github.com/WongMinHo/spring-boot-api-starter 特征 集成 Spring Boot 常用开发组件集 集成 Mybatis Plus、Mybatis Plus Generator组件;实现单表业务零SQL 集成 Atomikos 支持分布式事务、以及支持多数据源配置 统一异常处理 统一响应结果封装 基于 JWT 实现基于 Token 的鉴权机制 使用 Druid Spring Boot Starter 集成 Druid 数据库连接池与监控 使用 AutoGenerator 快速生成 Entity、Mapper、Mapper XML、Service、Controller 等各个模块的代码,极大的提升了开发效率,使团队代码风格保持统一 项目环境 中间件 版本 备注 JDK 1.8+ JDK1.8及以...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS8安装Docker,最新的服务器搭配容器使用
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS关闭SELinux安全模块
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2整合Redis,开启缓存,提高访问速度
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程