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

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

  •  
  •   Acceml · 111 天前 · 7395 次点击
    这是一个创建于 111 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

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

    说明:

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

    示例 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
        1
    stebest   111 天前
    最后一个循环 compare 没有左移
        2
    iDontEatCookie   111 天前
    你这种做法很容易想到啊。看到过一个好玩的解法,两个相同的数可以通过异或用一个变量找到,用一个数字的每一位去存而不是再开一个数组。既然每一位只能存两种状态,那么 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;
    };
        3
    rain0002009   111 天前
    我的天 楼主的这种解法竟然是很容易想到的吗
    作为一般人的思路不是应该
    先从小到大排个序 然后 3 个 3 个这么一取 只要第一个和第二个不相等 第一个就是那个数
    告诉我 不是只有我是这么想的
        4
    azh7138m   111 天前
    @rain0002009 就是个简单地状态转移,当时刚学数电(工科简易版本),写出来就是大概这个样子

    比最佳答案差得很多,主要是我不会化简状态(
        5
    ryd994   111 天前 via Android
    @rain0002009 排序至少 nlogn 复杂度
        6
    RicardoY   111 天前 via Android   ♥ 1
    这个解法使用了额外的空间啊...
        7
    honeyCream   111 天前
    线性的时间复杂度已经不符合了吧.应该只只能循环一次,你后面又加了一次循环.
        8
    tidyoux   111 天前
    那不叫 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)
        9
    b00tyhunt3r   111 天前 via iPad
    32 维数组? lz 知道 2 维数组啥样吗
        10
    no1xsyzy   111 天前
    想了想写了个通用的
    时间复杂度 O(n log k)
    空间复杂度 O(log k)
    其中 n 是数组的大小,k 是重复的个数

    每次使用 pattern 重新生成的话时间不变空间 O(1)
        11
    carlclone   111 天前 via Android
    @honeyCream 2On 也是 On 为什么不是线性
        12
    no1xsyzy   111 天前
    @honeyCream O(2*n) == O(n)
        13
    honeyCream   111 天前
    @carlclone 哈哈哈~好吧 我是想说最优的解法应该是 8 楼的 只循环一次😂
        14
    honeyCream   111 天前
    @carlclone 虽然我也不一定能写出来那种解法
        15
    honeyCream   111 天前
    @no1xsyzy 我的我的~我表述得有问题
        16
    yutonliu   111 天前
    虽然是算法题 不过 php 两个函数 就能解决了
        17
    lamada   111 天前
    这道题记得最佳解法是 异或
        18
    lamada   111 天前
    看错了,是三次
        19
    faustellar   111 天前
    之前见过一个类似的,如果是二进制每个元素逐位异或解决问题
    这里可以搞成三进制后,再定义一个异或(无进位加法)解决问题
        20
    xml123   111 天前   ♥ 2
    异或不就是模 2 加法,这里换成模 3 加法就行了啊
        21
    wenzhoou   111 天前 via Android
    @xml123 楼上一句话就说出了本质。
        22
    Yyyye   111 天前 via Android
    @azh7138m 能不能解释下这个
        23
    EthanDon   111 天前
    模 3 加法,可以的
        24
    azh7138m   111 天前
    @Yyyye 和最佳答案一个意思,就是一个 0 -> 1 -> 2 -> 0 的状态循环
    现在做我肯定选三个变量那个最优解
    4 年过去了,我的数电早还给老师了(
        25
    azh7138m   111 天前
    @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,要保存一下
    大概就是这么个意思,我记得是枚举出所有的情况,写到一个表上,然后画电路图(
    这玩意我记得拿逻辑门做汽车尾灯花式闪烁上用到过(
        26
    churchmice   110 天前 via Android   ♥ 2
    @azh7138m 卡诺图
        27
    Yyyye   110 天前 via Android
    @azh7138m 看来要学习下数电了
        28
    azh7138m   110 天前 via Android
    @churchmice 好像是这个,唉都忘记了。。。
        29
    qwertyegg   110 天前
    也写了个 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;
    }
    }
    }
    ~~~
        30
    qwertyegg   110 天前
    也写了个 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}));

    }
    }
    ```
        31
    qwertyegg   110 天前
    orz,跪了!
        32
    valleyboy   110 天前 via Android
    求和 取余 右移 数制转换 循环
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2482 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 35ms · UTC 15:10 · PVG 23:10 · LAX 08:10 · JFK 11:10
    ♥ Do have faith in what you're doing.