of04只出现一次的 数字

leecode

题目描述

给你一个整数数组 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 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/WGki4K 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

哈希表就不用了,用过太多次了,而且消耗大量空间, 我们直接进阶,用o(1)来解决

法1

排序法 很简单,就是先对数组排序,然后遍历出单个数据

sort.Ints(nums)//go语言自带的排序方法

查找只出现一次的数字

for i := 1; i < len(nums)-1; i++ {//查找只出现一次的数
  if nums[i] != nums[i-1] && nums[i] != nums[i+1] {
   return nums[i]
  }
 }

法2

执行结果

法1

func singleNumber2(nums []int) int {
 sort.Ints(nums)//go语言自带的排序方法
 if len(nums) == 1 {//去掉字符串长度为 0
  return nums[0]
 }
 if nums[0] != nums[1] {//排除首个数字不同
  return nums[0]
 }
 for i := 1; i < len(nums)-1; i++ {//查找只出现一次的数
  if nums[i] != nums[i-1] && nums[i] != nums[i+1] {
   return nums[i]
  }
 }
 return nums[len(nums)-1]//最后一个数只出现一次
}

执行用时： 8 ms , 在所有 Go 提交中击败了 27.66% 的用户 内存消耗： 3.2 MB , 在所有 Go 提交中击败了 62.41% 的用户 通过测试用例： 14 / 14 优化

// 优化2
func singleNumber3(nums []int) int {
 if len(nums) == 1 {
  return nums[0]
 }
 sort.Ints(nums)
 if nums[0] != nums[1] {
  return nums[0]
 }
 for i := 3; i < len(nums)-1; i = i + 3 {//优化部分因为是三个一起出现,所以当相同 的时候就直接跳3个就可以了
  if nums[i] != nums[i+1] {
   return nums[i]
  }
 }
 return nums[len(nums)-1]
}

执行用时： 4 ms , 在所有 Go 提交中击败了 92.20% 的用户 内存消耗： 3.2 MB , 在所有 Go 提交中击败了 62.41% 的用户 通过测试用例： 14 / 14

法2

数字电路设计 还没看懂

a = (~a & b & x) | (a & ~b & ~x)
b = ~a & (bˆ x)

func singleNumber(nums []int) int {
    a, b := 0, 0
    for _, num := range nums {
        b = (b ^ num) &^ a
        a = (a ^ num) &^ b
    }
    return b
}

执行用时： 4 ms , 在所有 Go 提交中击败了 92.20% 的用户 内存消耗： 3.3 MB , 在所有 Go 提交中击败了 60.99% 的用户 通过测试用例： 14 / 14