?本文，講位運算——異或運算。因為題干中說明要線性時間復(fù)雜度，所以采用位運算進行操作，而沒有采用哈希表。

目錄

1.只出現(xiàn)一次的數(shù)字 I

?2.只出現(xiàn)一次的數(shù)字 II

?3.只出現(xiàn)一次的數(shù)字 III

1.只出現(xiàn)一次的數(shù)字 I

136. 只出現(xiàn)一次的數(shù)字 - 力扣（LeetCode）

題目：

給你一個 非空整數(shù)數(shù)組 nums ，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

你必須設(shè)計并實現(xiàn)線性時間復(fù)雜度的算法來解決此問題，且該算法只使用常量額外空間。

示例 1 ：

輸入：nums = [2,2,1]

輸出：1

從一個成對數(shù)組中找到落單的元素。很顯然我們可以使用異或運算。（相同為0，不同為1）

• 兩個相同數(shù)字做異或運算，結(jié)果為0?？梢詭臀覀兣懦舫蓪Φ臄?shù)字。
• 0和任何數(shù)字進行異或運算，都得到這個數(shù)字本身。

代碼：

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

?2.只出現(xiàn)一次的數(shù)字 II

137. 只出現(xiàn)一次的數(shù)字 II - 力扣（LeetCode）?

題目：

給你一個整數(shù)數(shù)組?nums ，除某個元素僅出現(xiàn) 一次 外，其余每個元素都恰出現(xiàn) 三次 。請你找出并返回那個只出現(xiàn)了一次的元素。

你必須設(shè)計并實現(xiàn)線性時間復(fù)雜度的算法且不使用額外空間來解決此問題。

示例 1：

輸入：nums = [2,2,3,2]

輸出：3?

????????本題，如果我們繼續(xù)簡單的使用異或，我們會發(fā)現(xiàn)最后結(jié)果是2^3，沒辦法得到正確答案。我們可以換個思路題中強調(diào)每個元素恰好出現(xiàn)三次，我們從次數(shù)的角度出發(fā)，考慮該位值為1的次數(shù)取模。

????????數(shù)的每一位只有0或1。首先我們考慮第一位，再依次類推直到第32位結(jié)束，答案元素的每一位為0或者為1我們都是已知，即得到該答案元素。

如果非答案元素第一位為0，則有：

• 答案元素第一位為0，總共0個1，0%3=0
• 答案元素第一位為1，總共1個1，1%3=1

如果非答案元素第一位為1，則有：

• 答案元素第一位為0，總共3個1，3%3=0
• 答案元素第一位為1，總共4個1，4%3=1

例子：?

代碼：?

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;    //統(tǒng)計值為1的次數(shù)
            for(auto& e:nums)
            {
                sum+=((e>>i)&1);
            }
            if((sum%3)==1)
            {
                res|=(1<<i);    //與0移位或運算
            }
        }
        return res;
    }
};

時間復(fù)雜度：O(n logC)，其中n是數(shù)組長度，C是數(shù)據(jù)范圍，本題int數(shù)據(jù)類型，logC=32。

空間復(fù)雜度：O(1)

?3.只出現(xiàn)一次的數(shù)字 III

260. 只出現(xiàn)一次的數(shù)字 III - 力扣（LeetCode）

題目：

給你一個整數(shù)數(shù)組?nums，其中恰好有兩個元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個元素。你可以按 任意順序 返回答案。

你必須設(shè)計并實現(xiàn)線性時間復(fù)雜度的算法且僅使用常量額外空間來解決此問題。

示例 1：?

輸入：nums = [1,2,1,3,2,5]

輸出：[3,5]

解釋：[5, 3] 也是有效的答案。

? ? ? ? 本題，還是在異或運算的基礎(chǔ)上進行拓展，我們觀察題目可以發(fā)現(xiàn)，這道題目對所有元素異或后的結(jié)果也是2個不同的元素進行異或，而其他元素頻數(shù)都是2如題目I一樣消除了。

????????也就是說我們可以直接從異或的結(jié)果得到啟發(fā)，某位值為1，就表明兩個答案在該位的值不同。我們可以從這個角度為出發(fā)點進行切入，對數(shù)組分組！兩個答案一定在不同的組中。

思路：

已知x^x==0。定義數(shù)組的異或和為該數(shù)組所有元素的異或。

• 求出nums的異或和xor，可知xor為兩個目標元素的異或。
• 找到xor中為1的二進制位，假設(shè)是第k位。這說明兩個目標元素在第k位上不相同。
• 根據(jù)第k位是0還是1，把nums分為兩組，這樣兩個目標元素一定位于不同的組。
• 分別求出兩組的異或和，即得到兩個目標元素。

例子：?

?代碼：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int>ans(2);
        int value=0;
        for(auto& e:nums)
        {
            value^=e;
        }
        int k=0;
        while((value&1)==0)
        {
            value>>=1;
            ++k;
        }
        int ans1=0,ans2=0;
        for(auto&e:nums)
        {
            if(((e>>k)&1)==0)
            {
                ans1^=e;
            }
            else
            {
                ans2^=e;
            }
        }
        ans[0]=ans1;
        ans[1]=ans2;
        return ans;
    }
};

?文章來源地址http://www.zghlxwxcb.cn/news/detail-413616.html

到了這里，關(guān)于【舉一反三】只出現(xiàn)一次的數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！