一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4181|回复: 9
收起左侧

[Leetcode] single number II

[复制链接] |试试Instant~ |关注本帖
windream1991 发表于 2014-12-10 12:47:07 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
leetcode题目如下:
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?

在网上看了解答,其中一种解法是用二进制模拟三进制,代码如下:
int singleNumber(int A[], int n) {
    int ones = 0, twos = 0, xthrees = 0;
    for(int i = 0; i < n; ++i) {
        twos |= (ones & A[i]);
        ones ^= A[i];
        xthrees = ~(ones & twos);
        ones &= xthrees;
        twos &= xthrees;
    }

    return ones;
}

我对循环内的代码看不太懂,想请教一下各位
mingmingya 发表于 2015-7-31 11:54:32 | 显示全部楼层
本帖最后由 mingmingya 于 2015-7-31 11:56 编辑

K number
cclass Solution {public:
    int singleNumber(vector<int>& nums) {
        int len = sizeof(int) * 8;
        int res = 0;
        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                sum += (nums[j] >> i) & 0x01;
            }
            res += (sum % 3) << i;
        }
        return res;
    }
};
时间:O(32*N),这是一个通用的解法,如果把出现3次改为 k 次,那么只需模k就行了。
回复 支持 1 反对 0

使用道具 举报

z928czzc 发表于 2014-12-11 01:39:58 | 显示全部楼层
其实只要理解什么是XOR就好。
A XOR B = (A+B)%进制。
如果是10进制,7 XOR 8 = (7+8)%10 = 5
一种思想就是把二进制XOR改成三进制XOR就好

所谓single number,其实就是bit统计
你可以按照 bit by bit 统计
single number II,你可以把bit加到一起
所有number第一bit的sum
所有number第二bit的sum...
然后sum%3 (bit by bit) 就是结果...

single number问题最难的是k number问题
Given an array of integers, every element appears X times except for k numbers (that only appear once). Find that k numbers.
回复 支持 1 反对 0

使用道具 举报

Adeath 发表于 2014-12-10 13:30:37 | 显示全部楼层
本帖最后由 Adeath 于 2014-12-11 01:16 编辑

这个是用ones 和 twos 分别表示两个bit,要实现计算3的倍数,这俩bit的变化规律是 (注意实际运算中A[ i ]就相当于1)
twos     ones
  0          0
  0          1
  1          0
  1          1
  0          0
当ones和twos都达到1时,用xthrees把他们都重置为0,这就是xthrees开始那三行的作用
那么前两行计数  他利用的规律是
第一行 计算twos : 当ones是0时,twos不变,(利用了 x|0==x) 当ones是1,twos变为1 ( ones 是1 twos 一定是0 而 0|x==x)
第二行 计算ones : 简单的xor,偶数次为0,奇数次为1
大概就是这么回事了
顺便贴个讨论里那个更简洁的代码  原理一样的
  1.     public int singleNumber(int[] A) {
  2.         int zeros=0, ones=0;
  3.         for (int i=0; i<A.length; i++){  // 00 -> 01 -> 10 -> 00
  4.             zeros = (zeros^A[i]) & ~ones;  // if bit1 is 1 we should put bit0 as 0, otherwise just count
  5.             ones = (ones^A[i]) & ~zeros;  // if bit0 is 1 we should put bit1 as 0, otherwise just count
  6.         }
  7.         return zeros|ones;
  8.     }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2014-12-11 01:10:05 | 显示全部楼层
Adeath 发表于 2014-12-10 13:30
这个是用ones 和 twos 分别表示两个bit,要实现计算3的倍数,这俩bit的变化规律是 (注意实际运算中A[ i ]就 ...

awesome!thanks!
回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2014-12-12 03:10:55 | 显示全部楼层
z928czzc 发表于 2014-12-11 01:39
其实只要理解什么是XOR就好。
A XOR B = (A+B)%进制。
如果是10进制,7 XOR 8 = (7+8)%10 = 5

其实就是有点不能理解为什么A XOR B = (A+B)%进制?“A XOR B”就是一个确定的数,后面的“进制”是可变的,这两个东西怎么能相等?
你下面说的这个方法我倒是能理解,当时提交的时候也是用这个方法过的,我只是看到另外那种解法对位运算这些东西有点看不懂所以贴出代码问问大家。
对于你最后提的那个k number, 我搜了一下网上能找到的只有X=2的解法,对于这个问题你有什么思路吗?
回复 支持 反对

使用道具 举报

z928czzc 发表于 2014-12-12 08:04:46 | 显示全部楼层
本帖最后由 z928czzc 于 2014-12-12 08:07 编辑

7+8 = 15 是十进制+定义
7+8 = F   是十六进制+定义

A XOR B = (A+B)%进制 这就是XOR的一种定义,结果就是和进制本身有关重复相加到进位,然后不进位而归零,叫做XOR,如果进位,就叫做加法

至于k number,k=3貌似能解决(还没严格还没确定)
至于k>3目前还不能理解,不过也超过了面试题的范畴了...知道k=2就足够了
回复 支持 反对

使用道具 举报

 楼主| windream1991 发表于 2014-12-12 11:15:15 | 显示全部楼层
z928czzc 发表于 2014-12-12 08:04
7+8 = 15 是十进制+定义
7+8 = F   是十六进制+定义

原来如此!

另外对于k number那题的解法方便贴个链接吗?
回复 支持 反对

使用道具 举报

z928czzc 发表于 2014-12-12 21:51:20 | 显示全部楼层
windream1991 发表于 2014-12-12 11:15
原来如此!

另外对于k number那题的解法方便贴个链接吗?

自己想的办法,哪来的链接。在一堆废纸中都找不到了~需要分情况讨论和reduce case
有时间不如多刷点leetcode,这已经out of interview level了...pat
回复 支持 反对

使用道具 举报

zenw 发表于 2014-12-15 05:18:51 | 显示全部楼层
Mark 一下 我之前也在纠结这题
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 07:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表