[LeetCode] 136.Single Number 單獨的數(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

這道題給了我們一個非空的整數(shù)數(shù)組，說是除了一個數(shù)字之外所有的數(shù)字都正好出現(xiàn)了兩次，讓我們找出這個只出現(xiàn)一次的數(shù)字。題目中讓我們在線性的時間復雜度內(nèi)求解，那么一個非常直接的思路就是使用 HashSet，利用其常數(shù)級的查找速度。遍歷數(shù)組中的每個數(shù)字，若當前數(shù)字已經(jīng)在 HashSet 中了，則將 HashSet 中的該數(shù)字移除，否則就加入 HashSet。這相當于兩兩抵消了，最終凡事出現(xiàn)兩次的數(shù)字都被移除了 HashSet，唯一剩下的那個就是單獨數(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();
    }
}

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

 異或運算的真值表如下：

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

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++實現(xiàn)LeetCode(136.單獨的數(shù)字)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)單獨的數(shù)字內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論