学编程
题意, 有一个N大小的数组, 数组里的数字在1到N之间, 有些数字出现2次, 有些数字出现1次. 请找出所有出现2次的数字. 要求时间复杂度是O(N) 空间复杂度是 O(1).
如果不考虑空间复杂度, 那么我们可以开一个O(n) 的哈希表来记录数字是否已经出现过了, 在C++里我们可以用 unordered_set 集合来实现 O(1) 的查找和插入.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int> r; unordered_set<int> hash; for (const auto &n: nums) { if (hash.count(n)) { // 已经出现过了 r.push_back(n); } else { hash.insert(n); // 添加到集合中 } } return r; } }; |
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> r;
unordered_set<int> hash;
for (const auto &n: nums) {
if (hash.count(n)) { // 已经出现过了
r.push_back(n);
} else {
hash.insert(n); // 添加到集合中
}
}
return r;
}
};因为数字的范围是在1到N 之间, 所以我们可以把相应数字坐标的元素给取反, 如果本来已经是负数了, 就代表这个数字的绝对值已经出现过了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int> r; for (auto i = 0; i < nums.size(); ++ i) { if (nums[abs(nums[i]) - 1] < 0) { // 已经出现过了 r.push_back(abs(nums[i])); } else { nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1]; } } return r; } }; |
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> r;
for (auto i = 0; i < nums.size(); ++ i) {
if (nums[abs(nums[i]) - 1] < 0) { // 已经出现过了
r.push_back(abs(nums[i]));
} else {
nums[abs(nums[i]) - 1] = -nums[abs(nums[i]) - 1];
}
}
return r;
}
};这样就不需要额外的空间, 并且时间复杂度也是 O(n).
英文: C++ Coding Exercise – Find All Duplicates in an Array
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK