- 01.题目要求
- 02.问题分析
- 03.实例代码
- 博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
- 链接地址：https://github.com/yangchong211/YCBlogs
- 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！
- 问题如下所示：
- 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
- 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
- 示例 1:
输入: [2,2,1] 输出: 1 - 示例 2:
输入: [4,1,2,1,2] 输出: 4
- 如下所示
/** * 我能想到的第一个方法就是把所有的值当成 Map 的key，出现的次数当成value * 最后次数为 1 的就是那个单个的 */ @RequiresApi(api = Build.VERSION_CODES.N) public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) + 1); } } return map.entrySet().stream().filter(r -> r.getValue() == 1).findFirst().get().getKey(); } /** * 看到重复元素，本能的想到 Set,可以考虑把出现两次的数字先添加到 Set 里面，然后再移除掉， * 最后剩下一个就是单个的值。 */ public int singleNumber1(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { if (!set.remove(num)) { set.add(num); } } return set.iterator().next(); } /** * 异或(^) 运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1） * 除了其中一个数字是一次外，其他的都是两次，相同的值异或结果为0，用0异或所有的值， * 最终结果就是那个单个的值。 */ public int singleNumber2(int[] nums) { int r = 0; for (int num : nums) { r ^= num; } return r; }
- 我的个人站点：
- github：https://github.com/yangchong211
- 知乎：https://www.zhihu.com/people/yczbj/activities
- 简书：http://www.jianshu.com/u/b7b2c6ed9284
- csdn：http://my.csdn.net/m0_37700275
- 喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
- 开源中国：https://my.oschina.net/zbj1618/blog
- 泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
- 邮箱：[email protected]
- 阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
- segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
- 掘金：https://juejin.im/user/5939433efe88c2006afa0c6e