[Leetcode] Single Number 單身數(shù)

gecko23 發(fā)布于2019-08-14 12:27 / 1076人閱讀

摘要：最新思路解法請(qǐng)?jiān)L問排序法復(fù)雜度時(shí)間空間思路先將數(shù)組排序，再遍歷一遍，找前后都不一樣的那個(gè)數(shù)即可。代碼累加所有數(shù)中該位的個(gè)數(shù)位異或法復(fù)雜度時(shí)間空間思路我們用三個(gè)變量分別記錄出現(xiàn)一次的數(shù)，出現(xiàn)兩次的數(shù)和出現(xiàn)三次的數(shù)。

Single Number I 最新思路解法請(qǐng)?jiān)L問：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?

排序法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(1)

思路

先將數(shù)組排序，再遍歷一遍，找前后都不一樣的那個(gè)數(shù)即可。

哈希表法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

遍歷一遍數(shù)組，用哈希表將每個(gè)數(shù)字出現(xiàn)的次數(shù)記下。然后再遍歷一遍數(shù)組找出出現(xiàn)次數(shù)為1的那個(gè)。也可以在第一遍遍歷的時(shí)候一旦出現(xiàn)三次就在表中刪去該數(shù)。

位操作法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

我們可以利用異或的特性。一個(gè)數(shù)異或0，得到這個(gè)數(shù)本身，一個(gè)數(shù)異或本身，得到0。所以我們把所有數(shù)異或一遍，出現(xiàn)兩次的數(shù)就變成0，一次的數(shù)就是本身，留下來了。

代碼

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?

位計(jì)數(shù)法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

如果把所有數(shù)的每一位多帶帶累加起來的話，如果這一位累加和是3的倍數(shù)，說明出現(xiàn)一次的那個(gè)書在這一位肯定是0，不然肯定有3*n+1個(gè)1。同理，如果不是3的倍數(shù)，則是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++){
                // 累加所有數(shù)中該位1的個(gè)數(shù)
                bits[i] += (nums[j] >> i) & 1;
            }
            res |= (bits[i] % 3) << i;
        }
        return res;
    }
}

位異或法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

我們用三個(gè)變量分別記錄出現(xiàn)一次的數(shù)，出現(xiàn)兩次的數(shù)和出現(xiàn)三次的數(shù)。出現(xiàn)一次ones的數(shù)計(jì)算方法和I是一樣的，異或就行了。出現(xiàn)兩次twos的條件是ones中有該數(shù)，而該數(shù)又出現(xiàn)了。出現(xiàn)三次threes的條件是即出現(xiàn)在ones里又出現(xiàn)twos里。如果一個(gè)數(shù)出現(xiàn)了3次，我們就要把ones和twos中清除該數(shù)。

代碼

public class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0, threes = 0;
        for(int i = 0; i < nums.length; i++){
            // 出現(xiàn)兩次twos的條件是ones中有該數(shù)，而該數(shù)又出現(xiàn)了
            twos |= ones & nums[i];
            // 出現(xiàn)一次ones的數(shù)計(jì)算方法和I是一樣的，異或就行了
            ones ^= nums[i];
            // 出現(xiàn)三次threes的條件是即出現(xiàn)在ones里又出現(xiàn)twos里
            threes = ones & twos;
            // 將出現(xiàn)三次的數(shù)從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?

分組異或法 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

因?yàn)橛袃蓚€(gè)只出現(xiàn)1次的變量，所以我們將所有數(shù)字一起異或后得到的數(shù)實(shí)際上是這兩個(gè)數(shù)異或的結(jié)果。對(duì)于這個(gè)結(jié)果，如果某一位是0，那么這兩個(gè)數(shù)在這一位上有可能都是0，或者都是1。如果某一位是1，那么這兩個(gè)數(shù)載這一位上一定是不一樣的，一個(gè)是1，一個(gè)是0，才能異或出1。所以我們隨便找一位是1的（除非兩個(gè)數(shù)相等，不然不可能沒有一位是1），將所有數(shù)中這一位是1的分一組，這一位是0的分一組。這樣兩個(gè)數(shù)肯定在兩個(gè)不同組里。我們對(duì)兩個(gè)組分別異或，就能得到兩個(gè)數(shù)。

代碼

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];
        }
        // 找出最右邊第一個(gè)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;
    }
}