39 - 只出现一次的数字

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

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

示例 1:

输入: [2,2,1] 输出: 1

示例 2:

输入: [4,1,2,1,2] 输出: 4

解答

哈希表

var singleNumber = function (nums) {
  let a = new Map()
  for (const item of nums) {
    if (a.has(item)) {
      a.delete(item)
    } else {
      a.set(item, item)
    }
  }
  let result = 0
  a.forEach((item) => result = item)
  return result
};

Runtime: 80 ms, faster than 31.01% of JavaScript online submissions for Single Number.
Memory Usage: 37.8 MB, less than 25.10% of JavaScript online submissions for Single Number.

最后获得结果的方法有点傻，也想不到更好的方法了。map能用keys()或values()来打印现有的值，但是是Iterator 对象，也不知道怎么用，就只能这样了。

排序

var singleNumber = function (nums) {
  nums.sort((a, b) => a - b)
  for (var i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i + 1]) {
      i++;
    } else {
      return nums[i]
    }
  }
};

Runtime: 60 ms, faster than 74.00% of JavaScript online submissions for Single Number.
Memory Usage: 36.4 MB, less than 60.30% of JavaScript online submissions for Single Number.

func singleNumber(nums []int) int {
    sort.Ints(nums)
    fmt.Println("nums", nums)
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] == nums[i+1] {
            i++
        } else {
            return nums[i]
        }
        runtime.Gosched()
    }
    return nums[len(nums)-1]
}

Runtime: 20 ms, faster than 9.65% of Go online submissions for Single Number.
Memory Usage: 5.7 MB, less than 21.62% of Go online submissions forSingle Number.

数学法

官网的题解，一个很神奇的数学公式：$2∗(a+b+c)−(a+a+b+b+c)=c$

查了一圈发现js没有数组相加的，就只能自己手写一份了。

var singleNumber = function (nums) {
  const sets = new Set(nums)
  const sum = function (arr) {
    let sums = 0
    for (const item of arr) {
      sums += item
    }
    return sums
  }
  return 2 * sum(sets) - sum(nums)
};

Runtime: 60 ms, faster than 74.00% of JavaScript online submissions for Single Number.
Memory Usage: 37.6 MB, less than 33.34% of JavaScript online submissions for Single Number.

func map2Slice(m map[int]int) []int {
    s := make([]int, 0, len(m))
    for _, elem := range m {
        s = append(s, elem)
    }
    return s
}

func sum(arr []int) int {
    result := 0
    for _, elem := range arr {
        result += elem
        runtime.Gosched()
    }
    return result
}

func singleNumber(nums []int) int {
    set := map[int]int{}
    for _, elem := range nums {
        set[elem] = elem
        runtime.Gosched()
    }
    s := map2Slice(set)
    sum1 := sum(s)
    sum2 := sum(nums)
    return 2*sum1 - sum2
}

Runtime: 20 ms, faster than 9.65% of Go online submissions for Single Number.
Memory Usage: 6 MB, less than 10.81% of Go online submissions forSingle Number.

总感觉好心累哦。。js当中一些基本的函数，go里面都没有，需要现场写。map转slice也就算了，sum一个array都没有。。

或者可能有，需要掉什么包，反正没查到。。。

异或

相异为1，相同为0

a⊕0=a
a⊕a=0
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
满足交换律和结合律

因此只需要将所有的数进行 XOR 操作，留下来的就是那个唯一的数字。

js中的异或操作是^=

var singleNumber = function (nums) {
  let result = 0
  for (const item of nums) {
    result ^= item
  }
  return result
};

Runtime: 60 ms, faster than 74.00% of JavaScript online submissions for Single Number.
Memory Usage: 36.8 MB, less than 53.19% of JavaScript online submissions for Single Number.

func singleNumber(nums []int) int {
    result := 0
    for _, elem := range nums {
        result ^= elem
        runtime.Gosched()
    }
    return result
}

Runtime: 20 ms, faster than 9.65% of Go online submissions for Single Number.
Memory Usage: 4.7 MB, less than 62.16% of Go online submissions forSingle Number.

Previous51 - 从不订购的客户 Next189 - 347 前k个高频元素

Last updated 5 years ago

Was this helpful?