题目

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

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

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

提示：1 <= nums.length <= 3 * 104

-231 <= nums[i] <= 231 - 1

nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

解题思路分析

1、哈希辅助；时间复杂度O(n)，空间复杂度O(n)

func singleNumber(nums []int) int {
   m := make(map[int]int)
   for _, v := range nums {
      m[v]++
   }
   for k, v := range m {
      if v == 1 {
         return k
      }
   }
   return 0
}

2、排序遍历；时间复杂度O(nlog(n))，空间复杂度O(1)

func singleNumber(nums []int) int {
   sort.Ints(nums)
   for i := 0; i < len(nums)-1; i = i + 3 {
      if nums[i] != nums[i+1] {
         return nums[i]
      }
   }
   return nums[len(nums)-1]
}

3、位运算；时间复杂度O(n)，空间复杂度O(1)

func singleNumber(nums []int) int {
   var res int
   for i := 0; i < 64; i++ {
      count := 0
      for j := 0; j < len(nums); j++ {
         if (nums[j]>>i)&1 == 1 {
            count++
         }
      }
      res = res | ((count % 3) << i) // 哪一位出现求余后1次，该位置为1
   }
   return res
}

4、位运算；时间复杂度O(n)，空间复杂度O(1)

func singleNumber(nums []int) int {
   a, b := 0, 0
   for i := 0; i < len(nums); i++ {
      a = (a ^ nums[i]) & (^b) // a：保留出现1次的数
      b = (b ^ nums[i]) & (^a) // b：保留出现2次的数
   }
   return a // 最后返回只出现1次的数
}

5、数学计算；时间复杂度O(n)，空间复杂度O(n)

func singleNumber(nums []int) int {
   m := make(map[int]int)
   sum := 0
   singleSum := 0
   for _, v := range nums {
      if m[v] == 0 {
         singleSum = singleSum + v
      }
      m[v] = 1
      sum = sum + v
   }
   return (singleSum*3 - sum) / 2
}

总结

Medium题目，本题同leetcode 137.只出现一次的数字II