V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  LeetCode

[Leetcode] 137.只出现一次的数字 II

  •  
  •   Acceml ·
    Acceml · 2019-07-04 09:04:39 +08:00 · 16096 次点击
    这是一个创建于 1729 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    说明:

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    输入: [2,2,3,2]
    输出: 3
    

    示例 2:

    输入: [0,1,0,1,0,1,99]
    输出: 99
    

    题解

    根据上一道题目的经验,我们很明确的知道不能用数数字的办法去解。考虑位运算的办法,找相关的性质。

    这个题其实就是求,在其他数都出现 k 次的数组中有一个数只出现一次,求出这个数。

    而上面那个 k 次的是有通用解法的。

    使用一个 32 维的数组,用这个 32 维的数组存储:

    [第 31 位 1 的总数, 第 30 位 1 的个数,…, 第 1 位 1 的个数]

    • 假如第 0 位 1 的个数是 k 的倍数,那么要求的这个数在该位一定是 0 ;

    • 若不是 k 的倍数,那么要求的这个数在该位一定是 1。

      因为假如说数组中的某些数在该位置是 1,那么因为这个数要么出现 k 次,那么出现 1 次。

    这样我们就可以找出只出现一次那个数的二进制表示形式。二进制如何转化为 10 进制呢?

    假如,按照上面的规则,最招找到的二进制为:

    A = [0, 0, 0, 0, 0, …, 1]

    因为异或操作是:相同为 0,不同为 1。

    那么久可以依次用 1, 2, 4, 8 … 和依次每一位异或,即可得到最终答案。

    第二部分可能不好理解,可以手动模拟下。

    class Solution {
        public int singleNumber(int[] nums) {
            // 有多少个相同的数字
            int N = 3;
            // [高位 1 的个数,...,低位 1 的个数]
            int[] bitNum = new int[32];
            
            for (int i = 0; i < nums.length; i++) {
                int compare = 1;
                int num = nums[i];
                for (int j = bitNum.length - 1; j >= 0; j--) {
                    if ((compare&num) != 0) {
                        bitNum[j]++;
                    }
                    compare = compare << 1;
                }
            }
            
            int compare = 1;
            int res = 0;
            for(int i = bitNum.length - 1; i >= 0; i--) {
                if(bitNum[i] % N != 0) {
                    res = res ^ compare;
                }
            }
            return res;
       }
    }
    

    热门阅读

    Leetcode 名企之路

    32 条回复    2019-07-05 18:43:30 +08:00
    stebest
        1
    stebest  
       2019-07-04 09:44:24 +08:00
    最后一个循环 compare 没有左移
    iDontEatCookie
        2
    iDontEatCookie  
       2019-07-04 09:52:52 +08:00
    你这种做法很容易想到啊。看到过一个好玩的解法,两个相同的数可以通过异或用一个变量找到,用一个数字的每一位去存而不是再开一个数组。既然每一位只能存两种状态,那么 k 个相同的数就可以用 logk 个变量找到。

    var singleNumber = function(nums) {
    let a = 0, b = 0;
    for (let x of nums) {
    b = (b ^ x) & ~a;
    a = (a ^ x) & ~b;
    }
    return b;
    };
    rain0002009
        3
    rain0002009  
       2019-07-04 10:26:29 +08:00
    我的天 楼主的这种解法竟然是很容易想到的吗
    作为一般人的思路不是应该
    先从小到大排个序 然后 3 个 3 个这么一取 只要第一个和第二个不相等 第一个就是那个数
    告诉我 不是只有我是这么想的
    azh7138m
        4
    azh7138m  
       2019-07-04 10:39:53 +08:00
    @rain0002009 就是个简单地状态转移,当时刚学数电(工科简易版本),写出来就是大概这个样子
    https://gist.github.com/muzea/a50a68397bb6936cb48d7e13d9a69f60
    比最佳答案差得很多,主要是我不会化简状态(
    ryd994
        5
    ryd994  
       2019-07-04 10:42:11 +08:00 via Android
    @rain0002009 排序至少 nlogn 复杂度
    RicardoY
        6
    RicardoY  
       2019-07-04 10:50:42 +08:00 via Android   ❤️ 1
    这个解法使用了额外的空间啊...
    honeyCream
        7
    honeyCream  
       2019-07-04 11:19:11 +08:00
    线性的时间复杂度已经不符合了吧.应该只只能循环一次,你后面又加了一次循环.
    tidyoux
        8
    tidyoux  
       2019-07-04 11:30:41 +08:00
    那不叫 32 维数组。

    很容易搜到符合题目要求的解:

    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;
    }

    [引用]( https://www.cnblogs.com/daijinqiao/p/3352893.html)
    b00tyhunt3r
        9
    b00tyhunt3r  
       2019-07-04 11:50:03 +08:00 via iPad
    32 维数组? lz 知道 2 维数组啥样吗
    no1xsyzy
        10
    no1xsyzy  
       2019-07-04 12:46:29 +08:00
    想了想写了个通用的
    时间复杂度 O(n log k)
    空间复杂度 O(log k)
    其中 n 是数组的大小,k 是重复的个数
    https://gist.github.com/no1xsyzy/8db2a861103289a45be254dd54f44d2c
    每次使用 pattern 重新生成的话时间不变空间 O(1)
    carlclone
        11
    carlclone  
       2019-07-04 12:49:01 +08:00 via Android
    @honeyCream 2On 也是 On 为什么不是线性
    no1xsyzy
        12
    no1xsyzy  
       2019-07-04 13:02:29 +08:00
    @honeyCream O(2*n) == O(n)
    honeyCream
        13
    honeyCream  
       2019-07-04 13:35:08 +08:00
    @carlclone 哈哈哈~好吧 我是想说最优的解法应该是 8 楼的 只循环一次😂
    honeyCream
        14
    honeyCream  
       2019-07-04 13:35:29 +08:00
    @carlclone 虽然我也不一定能写出来那种解法
    honeyCream
        15
    honeyCream  
       2019-07-04 13:36:24 +08:00
    @no1xsyzy 我的我的~我表述得有问题
    yutonliu
        16
    yutonliu  
       2019-07-04 16:49:21 +08:00
    虽然是算法题 不过 php 两个函数 就能解决了
    lamada
        17
    lamada  
       2019-07-04 18:48:32 +08:00
    这道题记得最佳解法是 异或
    lamada
        18
    lamada  
       2019-07-04 18:49:16 +08:00
    看错了,是三次
    faustellar
        19
    faustellar  
       2019-07-04 20:45:41 +08:00
    之前见过一个类似的,如果是二进制每个元素逐位异或解决问题
    这里可以搞成三进制后,再定义一个异或(无进位加法)解决问题
    xml123
        20
    xml123  
       2019-07-04 20:47:41 +08:00   ❤️ 2
    异或不就是模 2 加法,这里换成模 3 加法就行了啊
    wenzhoou
        21
    wenzhoou  
       2019-07-04 20:52:54 +08:00 via Android
    @xml123 楼上一句话就说出了本质。
    Yyyye
        22
    Yyyye  
       2019-07-04 21:11:43 +08:00 via Android
    @azh7138m 能不能解释下这个
    EthanDon
        23
    EthanDon  
       2019-07-04 21:19:35 +08:00
    模 3 加法,可以的
    azh7138m
        24
    azh7138m  
       2019-07-04 21:35:17 +08:00
    @Yyyye 和最佳答案一个意思,就是一个 0 -> 1 -> 2 -> 0 的状态循环
    现在做我肯定选三个变量那个最优解
    4 年过去了,我的数电早还给老师了(
    azh7138m
        25
    azh7138m  
       2019-07-04 22:11:33 +08:00
    @Yyyye 看了楼上的模 3 加法我想起来了…….
    o t 是 one 第一位 two 第二位的意思,其实就是实现了一个模 3 加法,所以算完只要把第一位的 one 返回出去就好了
    就是 00 01 10 三个状态的转移
    对于 one 假如高位不是 1,输入是 1,那就是 00 -> 01 就是 o^(*it) ,高位是 1 的时候,如果这次输入是 1,那么应该是 10 -> 00 就是 &(~(t&*it)) 这里对高位做了判断
    对于 two 如果高位和输入都是 1,那么就是 10 -> 00,所以是 ~(t&(*it)) ,对于其他的情况,~(t&(*it)) 结果都是 1,就看低位会不会进位,所以是 o&*it,最后 |t 是,高位是 1 低位是 0 输入是 0 对应这个场景
    oo 是因为我要先算 o,要保存一下
    大概就是这么个意思,我记得是枚举出所有的情况,写到一个表上,然后画电路图(
    这玩意我记得拿逻辑门做汽车尾灯花式闪烁上用到过(
    churchmice
        26
    churchmice  
       2019-07-04 23:47:24 +08:00 via Android   ❤️ 2
    @azh7138m 卡诺图
    Yyyye
        27
    Yyyye  
       2019-07-05 00:54:32 +08:00 via Android
    @azh7138m 看来要学习下数电了
    azh7138m
        28
    azh7138m  
       2019-07-05 01:41:43 +08:00 via Android
    @churchmice 好像是这个,唉都忘记了。。。
    qwertyegg
        29
    qwertyegg  
       2019-07-05 01:42:31 +08:00
    也写了个 solution
    ~~~
    public class Solution137 {
    public int singleNumber(int[] nums) {
    int[] bits = new int[32];
    for(int n : nums)
    addBits(n, bits);
    StringBuilder binarySB = new StringBuilder();
    for(int i = 31; i >= 0; i--) {
    binarySB.append(bits[i] % 3);
    }
    return (int)Long.parseLong(binarySB.toString(), 2);
    }
    private void addBits(int n, int[] bits){
    int i = 0;
    while(n != 0){
    bits[i] += n % 2;
    i++;
    n = n >>> 1;
    }
    }
    }
    ~~~
    qwertyegg
        30
    qwertyegg  
       2019-07-05 01:42:58 +08:00
    也写了个 solution(上面的 markdown 错了)
    ```
    public class Solution137 {
    public int singleNumber(int[] nums) {
    int[] bits = new int[32];
    for(int n : nums)
    addBits(n, bits);
    StringBuilder binarySB = new StringBuilder();
    for(int i = 31; i >= 0; i--) {
    binarySB.append(bits[i] % 3);
    }
    return (int)Long.parseLong(binarySB.toString(), 2);
    }
    private void addBits(int n, int[] bits){
    int i = 0;
    while(n != 0){
    bits[i] += n % 2;
    i++;
    n = n >>> 1;
    }
    }

    public static void main(String[] args) {
    System.out.println(new Solution137().singleNumber(new int[]{-2,-2,1,1,-3,1,-3,-3,-4,-2}));

    }
    }
    ```
    qwertyegg
        31
    qwertyegg  
       2019-07-05 01:43:18 +08:00
    orz,跪了!
    valleyboy
        32
    valleyboy  
       2019-07-05 18:43:30 +08:00 via Android
    求和 取余 右移 数制转换 循环
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1108 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 22:49 · PVG 06:49 · LAX 15:49 · JFK 18:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.