avatar

傅坦坦的个人博客

0和1的把戏

要分享的两个算法题都是用关于的知识求解的,先透露一下。
首先来看第 1 道题:


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?


题目给定一个整数数组,数组中除了一个整数外,其他都是成对出现的,要求得到那个特别的数。初看起来题目非常简单,排个序就好了,然后遍历一遍,这是大部分人最直观的想法,包括我,但是排序的最好复杂度为nlogn,再加上O(n)的遍历时间,结果一定为非线性时间。
题目希望能够linear runtime时间内完成,那么仅有一次遍历的机会。所以一定要在这次遍历的时候做一下文章。

题解:
遍历数组,直接异或! 相同为 0,相异为 1。举个例子,3,4,3。这三个数异或,可以先将 3 和 3 异或,相同的数异或之后,结果为 0,然后再与 4 异或,0 与任何数异或结果不变。得到的结果为 4.
代码如下(java):

public int singleNumber(int[] A) {
  int result = A[0];
  for (int i = 1; i < A.length; i++) {
    result = result ^ A[i];
  }
  return result;
}

接下来看第二道题:

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

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


和第一道题大同小异,只不过是相同的个数由 2 变为 3 了。思路肯定还是在一次遍历的时候完成所有工作,但是这次不能简单的异或了,因为三次的话直接以后又出问题了。

题解:
回过头来再看看第一道题,其实,在异或的时候,我们做的工作是,遇到第一个 3,记住这个 3 遇到一次,记为 1,当再次遇到 3 得时候,将再记录一次 3 遇到了两次,于是我们将 1 改为 0.注意,这里,我们使用了一个 bit 来表示 2 种状态。对于第二题来说,我们也可以使用这样的思路,不过这里有三个状态,所以我们至少使用 2 个 bit 来表示,到第一次遇到时候,记作 10,当第二次遇到时,记作 01,当第三次遇到时,记作 00。状态变化为00->10->01->00(0->1->2->3)
代码如下(C++):

int singleNumber(int A[], int n) {
  int ones = 0;
  int twos = 0;
  for (int i = 0; i < n; i++) {
    ones = (ones ^ A[i]) & (~twos);
    twos = (twos ^ A[i]) & (~ones);
  }
  return ones;
}
wechat

欢迎关注公众号