溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
傳送門:https://leetcode-cn.com/problems/find-the-duplicate-number/submissions/
給定一個包含 n + 1 個整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數(shù)。假設只有一個重復的整數(shù)，找出這個重復的數(shù)。
示例 1:
輸入: [1,3,4,2,2]
輸出: 2
示例 2:
輸入: [3,1,3,4,2]
輸出: 3
說明：
不能更改原數(shù)組（假設數(shù)組是只讀的）。
只能使用額外的 O(1) 的空間。
時間復雜度小于 O(n2) 。
數(shù)組中只有一個重復的數(shù)字，但它可能不止重復出現(xiàn)一次。
我的實現(xiàn)方法之前寫的博客也有，前提是數(shù)組中最大的 數(shù)要小于數(shù)組長度
int findDuplicate(int* nums, int numsSize) {
int k, yl, sl;
for (int n=0;n<numsSize;n++)
{
k = nums[n]&0xffff;
yl = nums[k];//目標 yl為那個位置上的加密數(shù)據(jù)
sl = yl >> 16;
sl++;
nums[k]=(sl<<16) |(yl&0xffff );
}
for (int g=0;g< numsSize;g++)
{
k = nums[g];
yl = k >> 16;
if (yl > 1)
{
printf("%d\n", g);
return g;
}
}
return 0;
}
速度還可以
就是修改了源數(shù)據(jù) 不知道在函數(shù)返回前再修改回去還可以不可以。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經查實，將立刻刪除涉嫌侵權內容。
