Leetcode_137_Single Number II
2024-08-29 16:39:19
本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/42877129
Given an array of integers, every element appears three times 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)这道题和Single Number类似,不过Single Number中是除了一个元素出现一次外,其余的都出现两次,这种情况可以直接用‘^’符号进行处理就行。但对于本题,由于技术有限,目前还没有想到比较简单的办法。本文下方采用的方法是可行的,只不过会占用额外的空间。
(3)本文解决该题的思想是:创建Map来保存数组中元素和元素出现的次数,在遍历数组的过程中,将出现的数字都存入Map中,这里还需进行一步过滤操作,就是每当遍历到的元素在Map中对应的值大于1时,就将该值保存到过滤List中,并从Map中移除该值,在后续的遍历中,如果遍历到的值存在于过滤List中,则跳过当前元素遍历下一元素,Map中最后剩余的元素即为出现一次的那个元素。
(4)希望本文对你有所帮助。
算法代码实现如下:
/** * @author liqq */ public int singleNumber(int[] A) { if (A == null || A.length == 0) return -1; if (A != null && A.length == 1) return A[0]; Map<Integer, Integer> maps = new HashMap<Integer, Integer>(); List<Integer> filter = new ArrayList<Integer>(); for (int i = 0; i < A.length; i++) { if (i == 0) { maps.put(A[i], 1); } else { if (!filter.contains(A[i])) { if (maps.get(A[i]) == null) { maps.put(A[i], 1); } else { maps.put(A[i], maps.get(A[i]) + 1); } if (maps.get(A[i]) > 1) { maps.remove(A[i]); filter.add(A[i]); } } } } return maps.keySet().toArray(new Integer[0])[0]; }
最新文章
- .NET Core 1.0.1 升级汇总
- mysql数据库存储过程异常处理
- XidianOJ 1120 Gold of Orz Pandas
- 各个平台的mysql重启命令
- TM1680的I2C的51例程
- 标准Dispose实现 (转)
- cocos中BatchNode精灵集合的使用
- 获取ListControl控件中(复选框)CheckBox的状态
- 【完美解决】2017打开MVC 4项目,cshtml页面提示‘当前上下文不存在名称model’
- spring容器启动扩展
- Socket层实现系列 — send()类发送函数的实现
- Appium -选择、操作元素
- 记录EntityValidationErrors的详细信息
- 111python
- 关于RabbitMQ一点
- 进阶的Redis之数据持久化RDB与AOF
- 转载:quartz详解:quartz由浅入深
- I01-通过查询资料库方式来监控Informatica调度情况
- ZigBee设备入网流程之关联方式
- redux connect的浅比较说明
热门文章
- ActionContext.getContext()用法
- java泛型总结(类型擦除、伪泛型、陷阱)
- VNC 登录上去灰屏,没有shell脚本,鼠标变成X
- Android Multimedia框架总结(一)MediaPlayer介绍之状态图及生命周期
- FFmpeg源代码简单分析:日志输出系统(av_log()等)
- 两种配置大数据环境的方法Ambari以及hadoop源代码安装的步骤
- Android开发学习之路--RxAndroid之操作符
- Android广播接收器Broadcast Receiver-android学习之旅(十二)
- Android Device Administration 设备管理器——实现一键锁屏
- Android初级教程启动定时器详解