[Leetcode] Single Number 单身数

gecko23 发布于2019-08-14 12:27 / 954人阅读

摘要：最新思路解法请访问排序法复杂度时间空间思路先将数组排序，再遍历一遍，找前后都不一样的那个数即可。代码累加所有数中该位的个数位异或法复杂度时间空间思路我们用三个变量分别记录出现一次的数，出现两次的数和出现三次的数。

Single Number I 最新思路解法请访问：https://yanjia.me/zh/2018/11/...

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?

排序法 复杂度

时间 O(NlogN) 空间 O(1)

思路

先将数组排序，再遍历一遍，找前后都不一样的那个数即可。

哈希表法 复杂度

时间 O(N) 空间 O(N)

思路

遍历一遍数组，用哈希表将每个数字出现的次数记下。然后再遍历一遍数组找出出现次数为1的那个。也可以在第一遍遍历的时候一旦出现三次就在表中删去该数。

位操作法 复杂度

时间 O(N) 空间 O(N)

思路

我们可以利用异或的特性。一个数异或0，得到这个数本身，一个数异或本身，得到0。所以我们把所有数异或一遍，出现两次的数就变成0，一次的数就是本身，留下来了。

代码

public class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i = 0 ; i < nums.length; i++){
            res ^= nums[i];
        }
        return res;
    }
}

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?

位计数法 复杂度

时间 O(N) 空间 O(1)

思路

如果把所有数的每一位多带带累加起来的话，如果这一位累加和是3的倍数，说明出现一次的那个书在这一位肯定是0，不然肯定有3*n+1个1。同理，如果不是3的倍数，则是1。

代码

public class Solution {
    public int singleNumber(int[] nums) {
        int[] bits = new int[32];
        int res = 0;
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < nums.length; j++){
                // 累加所有数中该位1的个数
                bits[i] += (nums[j] >> i) & 1;
            }
            res |= (bits[i] % 3) << i;
        }
        return res;
    }
}

位异或法 复杂度

时间 O(N) 空间 O(1)

思路

我们用三个变量分别记录出现一次的数，出现两次的数和出现三次的数。出现一次ones的数计算方法和I是一样的，异或就行了。出现两次twos的条件是ones中有该数，而该数又出现了。出现三次threes的条件是即出现在ones里又出现twos里。如果一个数出现了3次，我们就要把ones和twos中清除该数。

代码

public class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0, threes = 0;
        for(int i = 0; i < nums.length; i++){
            // 出现两次twos的条件是ones中有该数，而该数又出现了
            twos |= ones & nums[i];
            // 出现一次ones的数计算方法和I是一样的，异或就行了
            ones ^= nums[i];
            // 出现三次threes的条件是即出现在ones里又出现twos里
            threes = ones & twos;
            // 将出现三次的数从ones和twos中去除
            twos &= ~threes;
            ones &= ~threes;
        }
        return ones;
    }
}

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

分组异或法 复杂度

时间 O(N) 空间 O(1)

思路

因为有两个只出现1次的变量，所以我们将所有数字一起异或后得到的数实际上是这两个数异或的结果。对于这个结果，如果某一位是0，那么这两个数在这一位上有可能都是0，或者都是1。如果某一位是1，那么这两个数载这一位上一定是不一样的，一个是1，一个是0，才能异或出1。所以我们随便找一位是1的（除非两个数相等，不然不可能没有一位是1），将所有数中这一位是1的分一组，这一位是0的分一组。这样两个数肯定在两个不同组里。我们对两个组分别异或，就能得到两个数。

代码

public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        int n = 0;
        for(int i = 0 ; i < nums.length; i++){
            n ^= nums[i];
        }
        // 找出最右边第一个1
        n = n & ~(n - 1);
        for(int i = 0 ; i < nums.length; i++){
            // 这一位是1的分一组
            if((nums[i] & n) == n){
                res[0] ^= nums[i];
            } else {
            // 不是1的分一组
                res[1] ^= nums[i];
            }
        }
        return res;
    }
}

云服务器私有云 single LeetCode single-spa LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64484.html

[LintCode/LeetCode] Single Number III

摘要：去掉最后一个保留最后一个保留最后一个保留第一个这道题在论坛里参考了和两位仁兄的解法。思想是将中所有的数进行异或运算。不同的两个数异或的结果，一定至少有一位为。最后，将和存入数组，返回。 Problem Given 2*n + 2 numbers, every numbers occurs twice except two, find them. Example Given [1,2,2...

lanffy 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Single Number I & II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
leetcode137. Single Number II

摘要：按照思路一和思路二很容易将这题解决。在这里，我们希望将出现三次的数字通过操作划掉。之后，我们使用和分别来记录第一位和第二位的情况。最后只出现一次的数值应该是保存在中，换句话说，最后应该全是。题目要求 Given an array of integers, every element appears three times except for one, which appears e...

mochixuan 2019-08-15 11:12 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：使用位运算数组只出现一次数字的数组得到最低的有效位，即两个数不同的那一位看完上面的解法，我脑海中只有问号的存在，啥意思啊下面就让我们简单了解一下位运算并解析一下这三道题目。另，负数按补码形式参加按位与运算。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只出现一次以外...

daydream 2019-05-21 11:41 评论0 收藏0
由三道 LeetCode 题目简单了解一下位运算

摘要：简单介绍一下位运算异或运算异或逻辑的关系是当不同时，输出当相同时，输出。另，负数按补码形式参加按位与运算。使一个数的最低位为零，可以表示为。，截止到这儿，三道题目中使用的位运算介绍完毕，那么这里我们插入一下的详细题解。你可做过这几道题？在面试的准备过程中，刷算法题算是必修课，当然我也不例外。某天，我刷到了一道神奇的题目： # 136. 只出现一次的数字给定一个非空整数数组，除了某个元素只...

刘明 2019-05-22 14:21 评论0 收藏0