首页 > 代码库 > Single Number II

Single Number II

题目:

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

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

技术分享

代码:

这个题目就一句话,看到后肯定会想到很多解决办法,但是:不能用更多的存储空间;还提示要用bit操作。

首先,我尝试了一下一般人都能想到的办法,就是排序之后挑出来前后都不一样的:

    public int singleNumber_old(int[] nums) {       
        if (nums==null) {
            return 0;
        }
        if (nums.length==1) {
            return nums[0];
        }
        sort_bubbling(nums);
        if (nums[0] != nums[1]) {
            return nums[0];
        }
         if (nums[nums.length-1] != nums[nums.length-2]) {
            return nums[nums.length-1];
        }
        for (int i = 1; i < nums.length-1; i++) {
            if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]) {
                return nums[i];
            }
        }
        return 0;
    }
    public void sort_bubbling(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = 0; j < nums.length-i-1; j++) {
                if(nums[j]>nums[j+1]) {
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

放进去后,不出所料的超时了,系统用了一串复制都复制不下的数字去测试~哎...技术分享

数了下,居然用了20002个这种大数字在测试~~~太暴力了!

有点懵逼啊!bit操作一直有点晕,百度了一下,原来这个算法很成熟了:

  这串int型的数字,变成二级制就是16位的0和1。

  由于每个数字都有三个,所以在每一个bit位上面无论是0还是1,都是3的倍数个,如果不是,说明这一位就是那个单个数字产生的。

  当然,我们只要看他产生的1在哪些位置上面,剩下的自然就是0的位置,然后就可以得出这儿数字。

  3个0或3个1相加之后对3取余都应该为0,因此取余不为1的位数组合起来就是那个 “Single Number”。

一个直接的实现就是用大小为 32的数组来记录所有 位上的和:

  public int singleNumber(int[] nums) {       
        int[] count = new int[32];
        int result = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (((nums[j] >> i) & 1)>0) {
                    count[i]++;
                }
            }
            result |= ((count[i] % 3) << i);
        }
        System.out.println(Integer.toBinaryString(result));
        return result;
    }

这个算法还不是最好了,百度到还有大神用掩码变量,我这里拷贝过来,供我们一起学习:)

这个算法是有改进的空间的,可以使用掩码变量:

  1. ones   代表第ith 位只出现一次的掩码变量
  2. twos  代表第ith 位只出现两次次的掩码变量
  3. threes  代表第ith 位只出现三次的掩码变量

假设在数组的开头连续出现3次5,则变化如下:

ones = 101
twos = 0
threes = 0
--------------
ones = 0
twos = 101
threes = 0
--------------
ones = 0
twos = 0
threes = 101
--------------

当第 ith 位出现3次时,我们就 ones  和 twos  的第 ith 位设置为0. 最终的答案就是 ones。

int singleNumber(int A[], int n) {
    int ones = 0, twos = 0, threes = 0;
    for (int i = 0; i < n; i++) {
        twos |= ones & A[i];
        ones ^= A[i];// 异或3次 和 异或 1次的结果是一样的
       //对于ones 和 twos 把出现了3次的位置设置为0 (取反之后1的位置为0)
        threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
    }
    return ones;
}

参考:http://oj.leetcode.com/discuss/857/constant-space-solution

 

Single Number II