題目描述

在一個數(shù)組 nums 中除一個數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)了三次。請找出那個只出現(xiàn)一次的數(shù)字。

題解一

先將數(shù)組排序，然后再找出現(xiàn)一次的數(shù)字是比較簡單的。

時間復(fù)雜度為，空間復(fù)雜度為。比較簡單，代碼省略。

題解二

還有一種想法是以空間換時間，使用一個哈希表來記錄數(shù)組中每個數(shù)字出現(xiàn)的次數(shù)，最終可以得到兩個只出現(xiàn)一次的數(shù)字。

時間復(fù)雜度為，空間復(fù)雜度為。比較簡單，代碼省略。

題解三

如果需要繼續(xù)優(yōu)化時空復(fù)雜度應(yīng)該怎么做呢？這里可以沿用上一題的思路，使用位運(yùn)算來解決。將所有數(shù)字的二進(jìn)制表示的每一位都進(jìn)行相加，如果某一位的和能夠被3整除，那么那個只出現(xiàn)一次的數(shù)字在這個位上就是0；若不能整除，那么那個只出現(xiàn)一次的數(shù)字在這個位上就是1。

下面是參考代碼：

import java.math.BigInteger;

class Solution {
    public int singleNumber(int[] nums) {
        StringBuilder sb = new StringBuilder(getFullBinaryString(0));
        for (int num : nums) {
            String numString = getFullBinaryString(num);
            for (int i = 0; i < 32; i++) {
                sb.setCharAt(i, (char) (sb.charAt(i)+numString.charAt(i)-'0'));
            }
        }

        for (int i = 0; i < 32; i++) {
            if ((int) (sb.charAt(i)) % 3 == 0)
                sb.setCharAt(i, '0');
            else sb.setCharAt(i, '1');
        }

        return Integer.valueOf(sb.toString(), 2);
    }

    public String getFullBinaryString(int num) {
        String s = Integer.toBinaryString(num);
        return String.format("%032d", new BigInteger(s));
    }
}

可以將這道題擴(kuò)展一下，若題目更改為：在一個數(shù)組 nums 中除一個數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)了n次。請找出那個只出現(xiàn)一次的數(shù)字。其實(shí)解法是相同的，具體的代碼就不寫啦~