題目:
**給定一個(gè)整數(shù)數(shù)組 a，其中1 ≤ a[i] ≤ n （n為數(shù)組長(zhǎng)度）, 其中有些元素出現(xiàn)兩次而其他元素出現(xiàn)一次。

創(chuàng)新互聯(lián)建站專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、道外網(wǎng)絡(luò)推廣、重慶小程序開發(fā)、道外網(wǎng)絡(luò)營(yíng)銷、道外企業(yè)策劃、道外品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供道外建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：jinyejixie.com

找到所有出現(xiàn)兩次的元素。

你可以不用到任何額外空間并在O(n)時(shí)間復(fù)雜度內(nèi)解決這個(gè)問題嗎？

示例：

輸入:
[4,3,2,7,8,2,3,1]

輸出:
[2,3]**

看題目條件給的數(shù)據(jù)大小我就想用計(jì)數(shù)排序,但是怎么不申請(qǐng)額外空間呢?
其實(shí)完全可以利用每個(gè)元素的高位數(shù)據(jù)保存信息. 但是要確定要保存的信息的范圍大小
比如你保存的是1-100 那你得給高8位留下來保存數(shù)據(jù) 底24位用來保存這個(gè)位置真實(shí)的數(shù)據(jù)值
leetcode上跑了還不錯(cuò)

int* findDuplicates(int* nums, int numsSize, int* returnSize) 
{
    //把每個(gè)元素的高16位和低16位分別保存2個(gè)信息點(diǎn)就可以了
    for (int m=0;m<numsSize;m++)
    {
        //每個(gè)元素的第16位才是其真正的值 因?yàn)楦?6位可能有其他值
        int realvalue = nums[m] &65535;//
        int high26 = nums[realvalue-1] >> 16;   //當(dāng)前的數(shù)字  //取下高16位
        int g16 = high26; //如果不是空
        g16++;
        nums[realvalue -1] = (nums[realvalue - 1]&65535) | (g16<<16);
    }
    //申請(qǐng)額外空間保存返回結(jié)果這個(gè)應(yīng)該不算額外空間吧
    int *result = malloc(sizeof(int)*numsSize);
    int cc = 0;
    for (int m = 0; m < numsSize; m++)
    {
        int high26 = (nums[m]>>16);
        if (2 == high26)
        {
            result[cc++] = m + 1;
        }
    //  printf("%d 出現(xiàn)%d次\n", m + 1, high26);
    }
    *returnSize = cc;
    return result;
}

時(shí)間

網(wǎng)站名稱：Leetcode442劃水記錄05
文章網(wǎng)址：http://jinyejixie.com/article32/pdsdsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、建站公司、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、服務(wù)器托管、定制開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)