[LeetCode] 136.Single Number 單獨(dú)的數(shù)字

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

這道題給了我們一個(gè)非空的整數(shù)數(shù)組，說是除了一個(gè)數(shù)字之外所有的數(shù)字都正好出現(xiàn)了兩次，讓我們找出這個(gè)只出現(xiàn)一次的數(shù)字。題目中讓我們?cè)诰€性的時(shí)間復(fù)雜度內(nèi)求解，那么一個(gè)非常直接的思路就是使用 HashSet，利用其常數(shù)級(jí)的查找速度。遍歷數(shù)組中的每個(gè)數(shù)字，若當(dāng)前數(shù)字已經(jīng)在 HashSet 中了，則將 HashSet 中的該數(shù)字移除，否則就加入 HashSet。這相當(dāng)于兩兩抵消了，最終凡事出現(xiàn)兩次的數(shù)字都被移除了 HashSet，唯一剩下的那個(gè)就是單獨(dú)數(shù)字了，參見代碼如下：

C++ 解法一：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> st;
        for (int num : nums) {
            if (st.count(num)) st.erase(num);
            else st.insert(num);
        }
        return *st.begin();
    }
};

Java 解法一：

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            if (!st.add(num)) st.remove(num);
        }
        return st.iterator().next();
    }
}

題目中讓我們不使用額外空間來做，本來是一道非常簡單的題，但是由于加上了時(shí)間復(fù)雜度必須是 O(n)，并且空間復(fù)雜度為 O(1)，使得不能用排序方法，也不能使用 HashSet 數(shù)據(jù)結(jié)構(gòu)。那么只能另辟蹊徑，需要用位操作 Bit Operation 來解此題，這個(gè)解法如果讓我想，肯定想不出來，因?yàn)檎l會(huì)想到用邏輯異或來解題呢。邏輯異或的真值表為：

 異或運(yùn)算的真值表如下：

由于數(shù)字在計(jì)算機(jī)是以二進(jìn)制存儲(chǔ)的，每位上都是0或1，如果我們把兩個(gè)相同的數(shù)字異或，0與0 '異或' 是0，1與1 '異或' 也是0，那么我們會(huì)得到0。根據(jù)這個(gè)特點(diǎn)，我們把數(shù)組中所有的數(shù)字都 '異或' 起來，則每對(duì)相同的數(shù)字都會(huì)得0，然后最后剩下來的數(shù)字就是那個(gè)只有1次的數(shù)字。這個(gè)方法確實(shí)很贊，但是感覺一般人不會(huì)往 '異或' 上想，絕對(duì)是為CS專業(yè)的同學(xué)設(shè)計(jì)的好題呀，贊一個(gè)~~ 

C++ 解法二：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto num : nums) res ^= num;
        return res;
    }
};

Java 解法二：

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
}

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(136.單獨(dú)的數(shù)字)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)單獨(dú)的數(shù)字內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論