您好,登錄后才能下訂單哦!
題目:
**給定一個整數(shù)數(shù)組 a,其中1 ≤ a[i] ≤ n (n為數(shù)組長度), 其中有些元素出現(xiàn)兩次而其他元素出現(xiàn)一次。
找到所有出現(xiàn)兩次的元素。
你可以不用到任何額外空間并在O(n)時間復雜度內(nèi)解決這個問題嗎?
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[2,3]**
看題目條件給的數(shù)據(jù)大小我就想用計數(shù)排序,但是怎么不申請額外空間呢?
其實完全可以利用每個元素的高位數(shù)據(jù)保存信息. 但是要確定要保存的信息的范圍大小
比如你保存的是1-100 那你得給高8位留下來保存數(shù)據(jù) 底24位用來保存這個位置真實的數(shù)據(jù)值
leetcode上跑了還不錯
int* findDuplicates(int* nums, int numsSize, int* returnSize)
{
//把每個元素的高16位和低16位分別保存2個信息點就可以了
for (int m=0;m<numsSize;m++)
{
//每個元素的第16位才是其真正的值 因為高16位可能有其他值
int realvalue = nums[m] &65535;//
int high26 = nums[realvalue-1] >> 16; //當前的數(shù)字 //取下高16位
int g16 = high26; //如果不是空
g16++;
nums[realvalue -1] = (nums[realvalue - 1]&65535) | (g16<<16);
}
//申請額外空間保存返回結(jié)果這個應該不算額外空間吧
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;
}
時間
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。