[Leetcode] Single Number 單身數

gecko23 發布于2019-08-14 12:27 / 1077人閱讀

摘要：最新思路解法請訪問排序法復雜度時間空間思路先將數組排序，再遍歷一遍，找前后都不一樣的那個數即可。代碼累加所有數中該位的個數位異或法復雜度時間空間思路我們用三個變量分別記錄出現一次的數，出現兩次的數和出現三次的數。

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

云服務器 GPU云服務器 single LeetCode single-spa LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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