文章目錄

• • 1. 題目信息
  • 2. 解題
  • • 2.1 BitMap
    • 2.2 set去重
    • 2.3 官方解題，快慢指針

1. 題目信息

給定一個包含 n + 1 個整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復(fù)的整數(shù)。假設(shè)只有一個重復(fù)的整數(shù)，找出這個重復(fù)的數(shù)。

示例 1:輸入: [1,3,4,2,2] 輸出: 2 示例 2:輸入: [3,1,3,4,2] 輸出: 3 說明：不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）。 只能使用額外的 O(1) 的空間。 時間復(fù)雜度小于 O(n2) 。 數(shù)組中只有一個重復(fù)的數(shù)字，但它可能不止重復(fù)出現(xiàn)一次。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

2.1 BitMap

參考位圖BitMap思想解題。

class Solution {//bitmap solution public:int findDuplicate(vector<int>& nums) {int idx, bit;int numOfBytes = (nums.size()-1)/8+1;char bytes[numOfBytes];memset(bytes,0,numOfBytes*sizeof(char));for(int i = 0; i < nums.size(); ++i){idx = nums[i]/8, bit = nums[i]%8;if(!(bytes[idx]&(1<<bit)))bytes[idx] |= (1<<bit);elsereturn nums[i];}return -1;} };

• 時間，空間復(fù)雜度均為O(n)

2.2 set去重

也可以用set集合來查重（set只能存儲不重復(fù)的key）

class Solution {//set solution public:int findDuplicate(vector<int>& nums) {set<int> s;for(int i = 0; i < nums.size(); ++i){if(s.find(nums[i]) == s.end())s.insert(nums[i]);elsereturn nums[i];}return -1;} };

2.3 官方解題，快慢指針

class Solution {//O(1)復(fù)雜度 public:int findDuplicate(vector<int>& nums) {int fast = nums[0], slow = nums[0];do{fast = nums[nums[fast]];slow = nums[slow];}while(fast != slow);fast = nums[0];while(fast != slow){fast = nums[fast];slow = nums[slow];}return fast;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 287. 寻找重复数（BitMap）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。