返回信息流Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
——————————————————————————————————————————————
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
unordered_map<int,int> m;
vector<int> v;
for(int i=0;i<nums.size();i++)
{
if(m.find(nums[i])!=m.end())
{
v.push_back(nums[i]);
}
m[nums[i]]=i;
}
return v;
}
};
——————————————————————————————————————————
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> v;
for(int i=0;i<nums.size();i++)
{
nums[abs(nums[i])-1]*=-1;
if(nums[abs(nums[i])-1]>0)
v.push_back(abs(nums[i]));
}
return v;
}
};
这是一条镜像帖。来源：北邮人论坛 / cpp / #94911同步于 2017/3/20
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
Find All Duplicates in an Array，两种解法复杂度是多少
bingge
2017/3/20镜像同步1 回复
订阅后，新回复会通过你的通知中心匿名送达。
1 条回复