LeetCode#136. Single Number

发表于 | 分类于 ， ，

LeetCode #136 Single Number

Given an 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?

分析

最容易想到的解法是利用HashMap，以数组中的数为key，以出现次数为value统计每一个整数出现的次数，然后遍历HashMap，取出出现次数为1的数。这样的话，线性时间就可以找出只出现一次的数字。

但是题目不仅要求线性时间，还问能不能使用额外的内存。分析一下题目，除了一个整数之外，其他每个整数都是成对出现的。利用计数的方法可以得出每个数字出现的次数，但是这必须要额外的空间。不需要额外空间的方式有两种，一种是修改数组中的元素，以突出唯一的元素；而另一个则是通过运算，使最后的结果等于唯一的数。

修改数组元素

要使用这种方法，必须保证不影响遍历的结果，因此这种方法只适用于很少一部分前提条件满足的情况。

如果这些数字都在[1, (nums.length + 1) / 2]中，我们可以通过对数字对应下标的数字取反的方式来得到只出现一次的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int findSingle(arary)      // array is the array of integers
  if (array.length = 0)
    return -1
  if (array.length = 1)
    return array[0]

  // 翻转下标为[n-1]的数字
  // 如果[n]出现了两次，那么[n-1]对应的数字最后一定是正数
  // 而如果只出现了一次，则为负数
  for (n in array)
    tmp = array[n - 1]
    tmp = tmp < 0 ? -tmp : tmp;
    array[tmp - 1] = -array[tmp - 1]

  // 找到唯一的一个负数，其下标+1即为唯一出现一次的整数
  for (i = 0, size = (arary.length + 1) >> 1; i < size; i++)
    if (array[i] < 0)
      return i + 1

  return -1

但是这种方案显然只适合于这种数组内元素都是从1到((array.length + 1) / 2)的连续正整数。

运算

我们需要找到一种运算最后能够得出唯一出现一次的数。四则运算显然不能满足要求，那么位运算呢？与？或？异或？异或？没错，两个相等的数异或为0，0与一个数异或可以得到该数。

1
2
3
4
5
6
7
8
9
int findSingle(array)
  if (array.length = 0)
    return -1
  
  result = 0
  for (n in array)
    result ^= n

  return result

简洁而优雅。