本專欄為c語言練習(xí)專欄，適合剛剛學(xué)完c語言的初學(xué)者。本專欄每天會(huì)不定時(shí)更新，通過每天練習(xí)，進(jìn)一步對(duì)c語言的重難點(diǎn)知識(shí)進(jìn)行更深入的學(xué)習(xí)。

今日練習(xí)題關(guān)鍵字：找到數(shù)組中消失的數(shù)字 哈希表

??博主csdn個(gè)人主頁(yè)：小小unicorn
?專欄分類：C語言天天練
??代碼倉(cāng)庫(kù)：小小unicorn的代碼倉(cāng)庫(kù)??
??????關(guān)注我?guī)銓W(xué)習(xí)編程知識(shí)

題目一：

題目描述：

寫一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。
數(shù)據(jù)范圍：兩個(gè)數(shù)都滿足
?10≤n≤1000
進(jìn)階：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度 O(1)

解題思路：

巧用位運(yùn)算： 1、num1 & num2，與運(yùn)算，得到的是2個(gè)數(shù)都是1的位置，如果進(jìn)行加法，則需要進(jìn)位，m =（num1 & num2）<< 1,得到進(jìn)位后的數(shù)。

2、num1 ^ num2,異或，得到的是2個(gè)數(shù)1個(gè)為0另一個(gè)為1的位置，如果進(jìn)行加法，則不需要進(jìn)位。n = num1 ^ num2,此時(shí)如果m + n得到的就是兩數(shù)之和，但不能做加法，此時(shí)我們想到了或運(yùn)算。但如果將m、n直接進(jìn)行或運(yùn)算，無法保證不進(jìn)位，于是我們重復(fù)以上的過程。

3、while(n & m)，當(dāng)n與上m得0 的時(shí)候，即再也不需要進(jìn)位了，此時(shí)將m | n返回即可。

代碼實(shí)現(xiàn)：

int Add(int num1, int num2 ) 
{
    int m = 0;
    int n = 0;
    m = (num1 & num2) << 1;  // 需要進(jìn)位
    n = num1 ^
        num2;        //無需進(jìn)位    此時(shí)m + n就是答案，但不能做加法
    while (n & m) 
    { // 檢查是否還需要進(jìn)位
        num1 = m;
        num2 = n;
        m = (num1 & num2) << 1;  //需要進(jìn)位
        n = num1 ^ num2;        //無需進(jìn)位
    }

    return m | n;
}

結(jié)果情況：

符合題目情況，問題解決。

題目二：

題目描述：

給你一個(gè)含 n 個(gè)整數(shù)的數(shù)組 nums ，其中 nums[i] 在區(qū)間 [1, n] 內(nèi)。請(qǐng)你找出所有在 [1, n] 范圍內(nèi)但沒有出現(xiàn)在 nums 中的數(shù)字，并以數(shù)組的形式返回結(jié)果。

解題思路：

我們可以用一個(gè)哈希表記錄數(shù)組 nums 中的數(shù)字，由于數(shù)字范圍均在 [1,n] 中，記錄數(shù)字后我們?cè)倮霉１頇z查 [1,n]中的每一個(gè)數(shù)是否出現(xiàn)，從而找到缺失的數(shù)字。

由于數(shù)字范圍均在 [1,n] 中，我們也可以用一個(gè)長(zhǎng)度為 nnn 的數(shù)組來代替哈希表。這一做法的空間復(fù)雜度是 O(n) 的。我們的目標(biāo)是優(yōu)化空間復(fù)雜度到 O(1)。

注意到 nums 的長(zhǎng)度恰好也為 n，能否讓 nums 充當(dāng)哈希表呢？

由于 nums 的數(shù)字范圍均在 [1,n]中，我們可以利用這一范圍之外的數(shù)字，來表達(dá)「是否存在」的含義。

具體來說，遍歷 nums，每遇到一個(gè)數(shù) x，就讓 nums[x?1] 增加 n。由于 nums 中所有數(shù)均在 [1,n] 中，增加以后，這些數(shù)必然大于 n。最后我們遍歷 nums，若 nums[i] 未大于 n，就說明沒有遇到過數(shù) i+1。這樣我們就找到了缺失的數(shù)字。

注意，當(dāng)我們遍歷到某個(gè)位置時(shí)，其中的數(shù)可能已經(jīng)被增加過，因此需要對(duì) n 取模來還原出它本來的值。

代碼實(shí)現(xiàn)：

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) 
{
    for (int i = 0; i < numsSize; i++) 
    {
        int x = (nums[i] - 1) % numsSize;
        nums[x] += numsSize;
    }
    int* ret = malloc(sizeof(int) * numsSize);
    *returnSize = 0;
    for (int i = 0; i < numsSize; i++) 
    {
        if (nums[i] <= numsSize) 
        {
            ret[(*returnSize)++] = i + 1;
        }
    }
    return ret;
}

結(jié)果情況：

符合題目要求，問題解決。

總結(jié)：

文章到這里就要告一段落了，有更好的想法或問題，歡迎評(píng)論區(qū)留言。
希望今天的練習(xí)能對(duì)您有所收獲，咱們下期見！文章來源地址http://www.zghlxwxcb.cn/news/detail-686608.html

到了這里，關(guān)于C語言每日一練--------Day(11)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！