题目描述

题目地址: https://leetcode-cn.com/problems/single-number

原题说的是给一个数组，它具有其中只有一个元素是只出现1次，其他元素都出现2次的特点。我们需要找到那个只出现1次的元素。

思路与实现

常规HashMap

第一想法能想到我们用Map统计每个元素出现的次数，直接贴实现没什么需要说的。

1234567891011121314151617181920212223242526class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i : nums) { if (map.containsKey(i)) { int count = map.get(i); count++; map.put(i, count); } else { map.put(i, 1); } } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { return entry.getKey(); } } return 0; }}

但其实这并不是这道题真正要考察的点，翻了评论才知道这道题考位运算，于是赶紧博客记录下来学习一波。

利用异或的性质

异或运算 ^ 具有一下3个性质：

交换律：$b$ ^ $a$ = $a$ ^ $b$$n$ ^ $0$ = $n$$n$ ^ $n$ = $0$

利用给的数组的特点，将每两个相同的元素利用交换律放在一起优先计算，再由于“相同元素异或为0“，成对的元素都变成了0，最后只剩下单个的那个元素即是我们需要的（本身异或0还是本身）。

实现也很简洁：

12345678910111213class Solution { func singleNumber(_ nums: [Int]) -> Int { var result:[Int] = 0 nums.map { res ^= $0 } return result } }

小结

位运算一看就蒙…遇到就记录一下。