题目描述

只出现一次的数字
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1:

  1. 输入：nums = [2,2,3,2]
  2. 输出：3

示例 2:

  1. 输入：nums = [0,1,0,1,0,1,100]
  2. 输出：100

提示：

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
    进阶：
    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

    解题思路

    先排序再扫描
    开始看觉得这题有点点难，后来一想，可以先排序，再顺序扫描一次即可，每次步长为三，因为存在三个同元素，所以每一步的三个元素必定相同，如果碰到了单一元素，一定就是找的那个元素。当然，这样子做就有点犯规的意思了😂。
    HashMap
    还有一种法子是HashMap，这种方法我开始并没有想到，我还是简单的、习惯性的想，造一个数组arr，利用数组的索引来当桶，比如，对于 [2,2,2,4]，顺序扫描，arr[2] = arr[2]+1，结果就是arr[2] = 3, arr[4] = 1。但是数的范围太大，这样子搞不现实。就是没想到HashMap。。这么合适的容器，我居然给忘了。。太久没用Java全忘完了。

    实现代码

    1. // 排序扫描
    2. public int singleNumber(int[] nums) {
    3. Arrays.sort(nums);
    4. for (int i = 0; i < nums.length-3; i+=3) {
    5.   if(nums[i]!= nums[i+1]){
    6.     return nums[i];
    7.   }
    8. }
    9. return nums[nums.length-1];
    10. }
    11. //HashMap
    12. public int singleNumber(int[] nums) {
    13.   HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();
    14.   for (int num : nums) {
    15.       int count = hashMap.getOrDefault(num, 0);
    16.       if (++count == 3) {
    17.           // 遇到三个元素的就从HashMap中删除，再也不会遇到了
    18.           hashMap.remove(num);
    19.       } else {
    20.           hashMap.put(num, count);
    21.       }
    22.   }
    23.   return (int) hashMap.keySet().toArray()[0];
    24. }

    时间及空间复杂度分析

    排序扫描的方式主要时间复杂度在于排序，一般是O(nlogn)了，一遍扫描就是O(n)总体是O(nlogn)，空间复杂度是原地排序O(1)
    HashMap方式的时间复杂度是O(n)，空间复杂度O(n)
    image.pngimage.png
    本以为HashMap的方式要比排序快，但结果却是排序更快。不过测试用例只有14个，不具有参考性。

    拓展思路

    官方题解：依次确定每一个二进制位
    用位运算的方法来解决，后面还有数字电路的方法。
    位运算Tips：使用位运算 (x >> i) & 1 得到 x 的第 i 个二进制位。
    image.png
    太离谱了🧎
    image.png