LeetCode 刷题笔记 - 第三期

时隔很长时间，再来一篇。挑选一道题，看上去是很简单的一道题，但是优化的算法比较难想到。~~（反正我是没想到 TAT）~~

而且这么长时间以后才发现题目是有编号的…所以今天的题目编号是 136

题目如下：

Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

大致意思就是给定一个非空整数数组，找出只出现一次的元素。要求是线性时间复杂度和不使用额外的内存空间。

例如：给定数组为：[1,2,1,2,3]，输出结果为 3

思考

第一想法很简单，强行遍历比对：

func singleNumber(nums []int) int {
  for i := 0; i < len(nums); i++ {
    f := nums[i]
    isFound := false
    for j := 0; j < len(nums); j++ {
      if j != i && nums[j] == f {
        isFound = true
        break
      }
    }
    if !isFound {
      return f
    }
  }
  return 0
}

逻辑不多说，这个算法没有利用额外的内存空间，但是时间复杂度为 O(n^2)，是比较低效的，那么这里就需要优化了。

再思考

再次审题，发现这个题目和之前的一道题目很相似啊，就是有序数组的去重复元素，那道题目解决方法的时间复杂度为 O(n)，所以如果这道题目先把无需数组排序以后再查找重复的，那么时间复杂度肯定是小于 O(n^2) 的，因为快速排序的时间复杂度为 nlog(n)。

按照这个思路实现如下：

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

首先使用排序方法排序，Golang 的 Ints 排序采用快速排序算法，然后从数组的第一个元素开始遍历，然后以2递增，然后当前元素和前一个元素作比对，如果相同，则有相同元素，如果不相同，则前一个元素为不重复的元素，如果在遍历完成以后没有找到不重复的元素，则表示排序后不重复的元素在最后一个。

这个算法没有使用新的内存空间，时间复杂度为 O(n) + nlog(n)。

再再思考

我们的目标是 ~~（没有蛀牙）~~ 在保持不使用新的内存空间的前提下，时间复杂度优化到 O(n)。

因为我实在想不到了 ~~（真心不好意思说）~~，所以就去Google一下，然后真的找到了大神的实现方法，然后跪在屏幕前膜拜一下，方法为：

异或计算

Ok，什么叫异或？（赶紧给大学专业课老师烧一炷香吧），简单说就是如果两个数的二进制表示对应为如果相同则为 0，否则为 1。详细的解释去翻书吧。

那么异或计算的最典型的应用就是

1 ^ 3 ^ 1 = 3

所以一下就可以看出来了，把数组中每一个元素做异或运算，最终的结果就是不重复的那个元素了。（很巧妙吧，反正我是没想到，因为平时异或运算用的真心不多）。

实现如下：

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

简单的不能再简单了，所以就不解释了。

小结

这道题目算是比较简单的，但是要满足空间复杂度和时间复杂度，还是要用到一些不常用的知识，因为异或运算在平时用的很少，所以就几乎遗忘了。通过这道题，把异或计算重新捡起来，巧妙使用真的可以简化很多算法。