前言：內(nèi)容包括：題目，代碼實現(xiàn)，大致思路，代碼解讀

題目：

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

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

示例 1：

輸入：nums = [1,2,1,3,2,5]
輸出：[3,5]
解釋：[5, 3] 也是有效的答案。
示例 2：

輸入：nums = [-1,0]
輸出：[-1,0]
示例 3：

輸入：nums = [0,1]
輸出：[1,0]

代碼實現(xiàn)：

int* singleNumber(int* nums, int numsSize, int* returnSize)
{
    int ret = 0;
    int i = 0;
    for(i=0;i<numsSize;i++)
    {
        ret^=nums[i];
    }

    int pos = 0;
    for(i=0;i<32;i++)
    {
        if(((ret>>i)&1)==1)
        {
            pos = i;
            break;
        }
    }

    int*ret2 = (int*)calloc(2,sizeof(int));
    for(i=0;i<numsSize;i++)
    {
        if((nums[i]>>pos)&1==1)
        {
            ret2[0]^=nums[i];
        }
        else
        {
            ret2[1]^=nums[i];
        }
    }
    *returnSize = 2;
    return ret2;

}

大致思路：

分組異或：

僅有兩個數(shù)字只出現(xiàn)一次，其他數(shù)字均成對出現(xiàn)

異或：相同為0，相異為1

1 數(shù)組中的所有數(shù)字異或在一起，結果=只出現(xiàn)一次的兩個數(shù)字異或在一起

? ?比如：1,2,1,3,2,5

? ?異或：1^1^2^2^3^5 = 3^5

? ?3的二進制：0 1 1

? ?5的二進制：1 0 1

?藍色圈/紅色圈的這一位，若是某個數(shù)字在這一位上的值是1，成為一組

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 若是某個數(shù)字在這一位上的值是0，成為另外一組

?

2 將這兩個數(shù)字分至不同組，每組異或，結果 = 要找的數(shù)字

? ?比如：1,2,1,3,2,5

? ?分組只需要將只出現(xiàn)過一次的3和5分開即可

? ?第一組（紅色圈的位置上的值為0）：1 1 5?異或:1^1^3 = 0^3 = 3

? ?第二組（紅色圈的位置上的值為1）：2 2 3? 異或：2^2^5 = 0^5 = 5

代碼解讀：

part1

    int ret = 0;
    int i = 0;
    for(i=0;i<numsSize;i++)
    {
        ret^=nums[i];
    }

將數(shù)組中的所有數(shù)字異或在一起，最終只會留下要找的兩個數(shù)字異或在一起的結果

有了這個結果，我們就能將這兩個數(shù)字分開至不同的組

part2

    int pos = 0;
    for(i=0;i<32;i++)
    {
        if(((ret>>i)&1)==1)//找出能夠區(qū)分兩個僅出現(xiàn)過一次數(shù)字的位置
        {
            pos = i;
            break;
        }
    }

ret：僅出現(xiàn)過一次的兩個數(shù)字異或在一起的結果

ret共有32個比特位，每一個比特位都要來到最低位（第i個比特位右移i位來到最低位）與1按位與

按位與：&，兩個都是1，則結果為1，只要有一個為0，則結果為0文章來源地址http://www.zghlxwxcb.cn/news/detail-408087.html

part3

    int*ret2 = (int*)calloc(2,sizeof(int));
    for(i=0;i<numsSize;i++)
    {
        if((nums[i]>>pos)&1==1)//讓pos位上的值為1的所有數(shù)字異或成為一組
        {
            ret2[0]^=nums[i];
        }
        else
        {
            ret2[1]^=nums[i]; //讓讓pos位上的值為0的所有數(shù)字異或成為一組
        }
    }
    *returnSize = 2;
    return ret2;

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