1.只出现一次的数（136 - 易）
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 :
输入: [2,2,1] 输出: 1 输入: [4,1,2,1,2] 输出: 4
思路：
法1：本题比较常规的解法是用集合进行记录，最终返回集合中的唯一元素，代码实现如下，但这里空间复杂度O(n)！
法2：先排序后比较有没有落单的，落单返回，时间复杂度O(nlogn)，空间复杂度O(1)。
法3：根据异或对象相同为0，不同为1的规则，可以推导出一些性质
- 0 ⊕ a = a
- a ⊕ a = 0
此外，异或满足交换律以及结合律。
代码实现：
// 利用set集合 public int singleNumber(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (!set.contains(nums[i])) { set.add(nums[i]); } else { set.remove(nums[i]); } } return set.iterator().next(); // 返回集合中的唯一元素 }
ps：这里注意迭代器和数据结构中的链表一样，有个header指针，header->next()就是链表中第一个元素…… 如下所示：
pre 1 2 3 4
开始header指针指向pre，当执行一次iterator().next()就是返回指针所指的元素，即返回1，本题中返回那个唯一元素。
// 先排序 public int singleNumber(int[] nums) { if (nums.length == 1) return nums[0]; int i = 1; Arrays.sort(nums); for ( ; i < nums.length; i += 2) { if (nums[i] != nums[i - 1]) break; } return nums[i - 1]; } // 位运算 public int singleNumber(int[] nums) { int ans = 0; for (int i = 0; i < nums.length; i++) { ans ^= nums[i]; } return ans; }
2.只出现一次的数II（137 - 中）
题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 :
输入: [2,2,3,2] 输出: 3 输入: [0,1,0,1,0,1,99] 输出: 99
思路：
法1：和1不同的是，本题重复数字变成3个，可以用HashMap来实现计数，但时间复杂度O(n)；
法2：和案例1解法2思路相同，先排序，后比较；
法3：参考 这里 的一个解法。我们把数字放眼到二进制形式。
假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6 1 0 0 1 2 0 1 0 6 1 1 0 1 0 0 1 1 0 0 1 2 0 1 0 2 0 1 0 3 0 1 1 3 0 1 1 3 0 1 1 看最右边的一列 1001100111 有 6 个 1 再往前看一列 0110011111 有 7 个 1 再往前看一列 0010000 有 1 个 1 我们只需要把是 3 的倍数的对应列写 0，不是 3 的倍数的对应列写 1 也就是 1 1 0,也就是 6。
原因的话，其实很容易想明白。如果所有数字都出现了 3 次，那么每一列的 1 的个数就一定是 3 的倍数。之所以有的列不是 3 的倍数，就是因为只出现了 1 次的数多贡献出了 1。
所以所有不是 3 的倍数的列写 1（多出的数有贡献），其他列写 0（无贡献） ，就找到了这个出现 1 次的数。
本解法也可以进行推广，即是n的倍数列写1，其他列写0，找到其余元素都出现n次时，出现1次的元素。
代码实现：
class Solution { // hash计数 public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i : nums) { map.put(i, map.getOrDefault(i, 0) + 1); } for (int key : map.keySet()) { if (map.get(key) == 1) { return key; } } return -1; } // 排序（注意步长） public int singleNumber(int[] nums) { Arrays.sort(nums); int i = 2; for (; i < nums.length; i += 3) { if (nums[i] != nums[i - 2]) { break; } } return nums[i - 2]; } // 位运算 public int singleNumber(int[] nums) { int ans = 0; //考虑每一位 for (int i = 0; i < 32; i++) { int count = 0; //考虑每一个数 for (int j = 0; j < nums.length; j++) { //第j个数的i位是否为 1（统计第i位中1的个数） if ((nums[j] >>> i & 1) == 1) { count++; } } //1 << i,将1左移位，即将i位位置1 if (count % 3 != 0) { ans = ans | 1 << i; } } return ans; } }
3.只出现一次的数III（260 - 中）
题目描述：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例 :
输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。
思路：
法1：最直接的方法，统计每个数出现的次数。使用 HashMap 或者 HashSet，由于每个数字最多出现两次，我们可以使用 HashSet。
法2：先排序，后比较，但是有两个细节：（1）如何出来首尾（2）不同步长；
法3：位运算采用降维的思想，先获取两个不同元素（结果）的异或值，技巧：a & (-a)获取a二进制中的最右边的1。这样第二次遍历通过这个条件进行区分，类似进行两遍136题操作。
代码实现：
class Solution { // hashmap public int[] singleNumber(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); int[] ans = new int[2]; int i = 0; for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { ans[i++] = entry.getKey(); } } return ans; } // hashset public int[] singleNumber(int[] nums) { HashSet<Integer> set = new HashSet<>(); int[] ans = new int[2]; int index = 0; for (int num : nums) { if (!set.contains(num)) { set.add(num); } else { set.remove(num); } } for (int i : set) { ans[index++] = i; } return ans; } // 排序(注意不同的步长) public int[] singleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int[] ans = new int[2]; int index = 0; for (int i = 0; i < n - 1;) { if (nums[i] != nums[i + 1]) { ans[index++] = nums[i]; i++; } else { i += 2; } } // 最后一个如果只出现一次，最后一个元素会被上述for循环略过 if(nums[n - 2] != nums[n - 1]) { ans[index++] = nums[n - 1]; } return ans; } // 位运算 public int[] singleNumber(int[] nums) { int[] ans = new int[2]; int xor = 0; for (int num : nums) { xor ^= num; } // 获取两个数异或后二进制中最低非0位(即区分两个数) xor &= -xor; // 遍历数组与xor进行与操作，即把问题降维到136题 for (int num : nums) { if ((num & xor) == 0) { ans[0] ^= num; } else { ans[1] ^= num; } } return ans; } }
4.第一个只出现一次的字符（剑指50）
题目描述：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 :
s = "abaccdeff" 返回 "b" s = "" 返回 " "
思路：本题考查hash表：下面两种时间复杂度相同，不同的是有序hash需要遍历一次s串。
代码实现：
class Solution { // hash表 public char firstUniqChar(String s) { HashMap<Character, Integer> map = new HashMap<>(); char[] cs = s.toCharArray(); for (char c : cs) { map.put(c, map.getOrDefault(c, 0) + 1); } for (char c : cs) { if (map.get(c) == 1) { return c; } } return ' '; } // 有序hash表 public char firstUniqChar(String s) { HashMap<Character, Integer> map = new LinkedHashMap<>(); char[] cs = s.toCharArray(); for (char c : cs) { map.put(c, map.getOrDefault(c, 0) + 1); } for (Map.Entry<Character, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { return entry.getKey(); } } return ' '; } }
补充：
ps：注意先位运算再进行逻辑运算。java优先级口诀：单目乘除为（位）关系，逻辑三目后赋值。
- 单目：单目运算符+ –(负数) ++ -- 等
- 乘除：算数单目运算符* / % + -
- 为：位移单目运算符<< >> >>>
- 带符号右移>>（相当于除以2）：正数右移高位补0，负数右移高位补1。
- 无符号右移>>>：无论正数负数，高位统统补0。
- 关系：关系单目运算符> < >= <= == !=
- 逻辑：逻辑单目运算符&& || & | ^
- 三目：三目单目运算符A > B ? X : Y
- 后：无意义，仅仅为了凑字数
- 赋值：赋值 =
