今天為大家分享的是關(guān)于在數(shù)組中找到只出現(xiàn)一次數(shù)字的系列題目，我將使用c跟Java來實現(xiàn)，希望我的分享能夠幫助到大家。

初階查找單身狗

第一道題目是一個數(shù)組中只出有一個出現(xiàn)了一次的數(shù)字，也就是有一個單身狗。這是題目鏈接leetcode之只出現(xiàn)一次的數(shù)字

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

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

理解題目

根據(jù)題目給出的要求我們可以知道這個題目要求我們寫的代碼時間復(fù)雜度不超過O(N),時間復(fù)雜度也不能超過O(N),也就是說我們要盡可能的做到遍歷數(shù)組一遍并且不額外創(chuàng)建一個同樣大小的數(shù)組來解決這個題目。

做題思路

在做這個題之前，我們需要知道一個知識，那就是異或(^)位運算。二進(jìn)制位相同為0，相異為1。0異或任何數(shù)結(jié)果還是那個數(shù)，兩個相同的數(shù)異或結(jié)果為0。也就是說這個題我們只需要將數(shù)組的每一個元素全部都異或一遍，得到的最終結(jié)果就是那個只出現(xiàn)了一次的數(shù)字。

C語言代碼實現(xiàn)

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

Java代碼實現(xiàn)

class Solution {
    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0; i<nums.length; i++) {
            ret^=nums[i];
        }

        return ret;
    }
}

這個題想必大家應(yīng)該很容易理解吧，那么我們再來看一道進(jìn)階的找單身狗的問題。

進(jìn)階找單身狗

leedcode之只出現(xiàn)一次的數(shù)字（進(jìn)階）

題目要求

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

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

做題思路

這個題目跟上面其實思路是一樣的，只不過在這個數(shù)組里面有兩個只出現(xiàn)了一次的數(shù)字，我們還只是全部將他們異或一下，是不能得到最終結(jié)果的。所以這里我們需要稍稍做點改變，因為你數(shù)組里面如果只有一個單身狗，那么就是只需要全部異或一遍，那么如果數(shù)組里面有兩個的時候我們只需要將兩個只出現(xiàn)了一次的數(shù)字形象的放置在兩個不同的數(shù)組中，其他兩兩相同的數(shù)字只需要在一個數(shù)組中就可以了。那么想要做出來這道題的關(guān)鍵其實就是如何將這兩個只出現(xiàn)了一次的數(shù)字放在不同的數(shù)組中。

同樣的我們還是先將這個數(shù)組的所有元素異或一下，這個異或的結(jié)果其實就是那兩個只出現(xiàn)了一次的數(shù)字以獲得結(jié)果。然后我們再來看這個結(jié)果的二進(jìn)制位，因為我們前面說了，異或操作二進(jìn)制位相同為0，相異為1，我們只需要找到二進(jìn)制位1的地方，然后再將數(shù)組中所有元素相同的地方二進(jìn)制位0的放一組，為1的放另一組，最后再分別異或就找到了那兩個只出現(xiàn)了一次的數(shù)字。

C語言代碼實現(xiàn)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
    //動態(tài)開辟一個兩個元素為0的數(shù)組，用來存放兩個單身狗
    int* ans = (int*)calloc(2,sizeof(int));  
    int ret = 0;
    for(int i =0 ;i<numsSize; i++)
    {
        ret^=nums[i];
    }
    //pos用來記錄ret中哪個二進(jìn)制位為1
    int pos = 0;
    for(int i = 0; i<32; i++)
    {
        if((ret>>i)&1 == 1)
        {
            pos = i;
            break;
        }
    }
    for(int i = 0; i<numsSize; i++)
    {
        if((nums[i] >> pos)&1 == 1)
        {
            ans[0]^=nums[i];
        }
        else
        {
            ans[1]^=nums[i];
        }
    }

    *returnSize = 2;
    return ans;
}

Java代碼實現(xiàn)

class Solution {
    public int[] singleNumber(int[] nums) {
        int[] ans = new int[]{0,0};  
        int ret = 0;
        for(int i  =0; i<nums.length; i++) {
            ret^=nums[i];
        }
        int pos = 0;
        for(int i = 0; i<32; i++) {
            if(((ret>>i)&1) == 1) {
                pos = i;
                break;
            }
        }
        for(int i = 0; i<nums.length; i++) {
            if(((nums[i]>>pos)&1) == 1) {
                ans[0]^=nums[i];
            }else{
                ans[1]^=nums[i];
            }
        }
        return ans;
    }
}

小結(jié)

那么這些就是我今天為大家分享的知識，如有錯誤，請隨時指出，感謝大家的觀看。文章來源地址http://www.zghlxwxcb.cn/news/detail-406686.html

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