C++中LeetCode實現單獨數字的示例分析

這篇文章主要介紹了C++中LeetCode實現單獨數字的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

[LeetCode] 136.Single Number 單獨的數字

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

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

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 數據結構。那么只能另辟蹊徑，需要用位操作 Bit Operation 來解此題，這個解法如果讓我想，肯定想不出來，因為誰會想到用邏輯異或來解題呢。邏輯異或的真值表為：

 異或運算的真值表如下：

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

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

感謝你能夠認真閱讀完這篇文章，希望小編分享的“C++中LeetCode實現單獨數字的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!