劍指 Offer(C++版本)系列:劍指 Offer 03 數組中重複的數字

我是管小亮 2022-01-08 04:05:01 阅读数:975

offer c++ 版本 系列 offer

同步GitHub在此 https://github.com/TeFuirnever/GXL-Skill-Tree

1、題幹


找出數組中重複的數字。
在一個長度為 n 的數組 nums 裏的所有數字都在 0~n-1 的範圍內。
數組中某些數字是重複的,但不知道有幾個數字重複了,也不知道每個數字重複了幾次。
請找出數組中任意一個重複的數字。
示例 1:
輸入:
[2, 3, 1, 0, 2, 5, 3]
輸出:2 或 3
限制:
2 <= n <= 100000
通過次數330,298提交次數488,116

在這裏插入圖片描述

2、哈希錶

根據目前已經學習過的數據結構,很容易想到哈希錶,記錄數組中的各個數字的次數。當查到哪個數字的次數不是1,那麼一定有多個該數字,那麼將該重複數字直接返回。

算法流程:

  1. 初始化: 新建哈希錶 map,記為 hash,第一個比特置是數字,第二個比特置是次數;
  2. 遍曆數組 nums 中的每個數字 nums[i] :
    1. 將 nums[i] 添加至 hash 中;
    2. 當 nums[i] 在 hash 中的次數非 1,說明重複,直接返回 nums[i] ;
  3. 返回 -1 ,找不到重複的數字,返回 -1 。
//面試題03.數組中重複的數字
//map存儲
class Solution {

public:
int findRepeatNumber(vector<int>& nums) {

map<int, int> hash;
for(int i = 0; i < nums.size(); ++ i)
{

hash[nums[i]] ++ ;
if(hash[nums[i]] != 1) return nums[i];
}
return -1;
}
};

在這裏插入圖片描述

//等效代碼
class Solution {

public:
int findRepeatNumber(vector<int>& nums) {

//unordered_map<int, int> hash;
map<int, int> hash;
//for(int i = 0; i < nums.size(); ++ i)
for(int num : nums)
{

hash[num] ++ ;
if(hash[num] != 1) return num;
}
return -1;
}
};

3、原地置換

由於數組的長度是 n ,而數字也是 0 - n-1,因此可以使得索引與數組中該索引的數字相同,而同一個索引對應多個數字時必然重複了。

算法流程:

  1. 遍曆數組 nums 中的每個數字 nums[i] :
    1. 將 nums[i] == nums[nums[i]],說明該數字與該數字索引的數字相同;
    2. 當 nums[i] != nums[nums[i]],可以交換使之符合 1.1 中情况;
  2. 如果 nums[i] == i,說明交換有效果了,否則返回答案 nums[i] ;
  3. 返回 -1 ,找不到重複的數字,返回 -1
//面試題03.數組中重複的數字
//標准做法
class Solution {

public:
int findRepeatNumber(vector<int>& nums) {

for(int i = 0; i < nums.size(); ++ i)
{

while(nums[i] != nums[nums[i]]) swap(nums[i], nums[nums[i]]);
if(nums[i] != i) return nums[i];
}
return -1;
}
};

在這裏插入圖片描述

在這裏插入圖片描述
在這裏插入圖片描述

4、複雜度

/* 代碼中盡管有一個兩重循環,但每個數字最多只要交換兩次就能找到屬於它自己的比特置, 因此總的時間複雜度是O(n)。 另外,所有的操作步驟都是在輸入數組上進行的,不需要額外分配內存,因此空間複雜度為O(1)。 */

——————————————————————————————————————

—————————————————————————————————————

本文由 leetcode、牛客、公眾哈哦、知乎共同支持!
在這裏插入圖片描述
https://leetcode-cn.com/u/tefuirnever/
在這裏插入圖片描述
https://blog.nowcoder.net/wsguanxl
在這裏插入圖片描述
https://mp.weixin.qq.com/s/bDwxwQfZytIx4mAn8eK20Q

在這裏插入圖片描述
https://www.zhihu.com/people/tefuirnever_-.-

版权声明:本文为[我是管小亮]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080405006028.html