LeetCode之Find All Duplicates in an Array
程序员文章站
2022-07-15 13:05:50
...
本题的意思是给定一个整数数组,其中每个元素x都满足1 <= x <= n,其中n是该数组的元素数量。该数组中每个元素要么出现1次,要么出现2次。要求在不使用额外空间和在O(n)的时间复杂度内的条件下,找出所有出现2次的元素。
本题解法:从头至尾遍历该数组,将数组下标为当前访问的数组元素值减一的元素置为其本身的相反数(如果其本身现在是正数),那么如果以后再访问到与当前元素相同的元素,就会发现数组下标为当前访问的数组元素值减一的元素已经是负数了,就可以将这个当前访问的元素挑选出来,遍历完后,即可挑选出所有出现2次的元素。
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> dupl_;
for (int i = 0; i < nums.size(); ++i) {
int index = abs(nums[i]) - 1;
if (nums[index] < 0) {
dupl_.push_back(index + 1);
}
nums[index] = -nums[index];
}
return dupl_;
}
};
上一篇: Feign远程调用
推荐阅读
-
【一天一道LeetCode】#26. Remove Duplicates from Sorted Array
-
LeetCode448 — Find All Numbers Disappeared in an Array
-
LeetCode442 — Find All Duplicates in an Array
-
leetcode 448. Find All Numbers Disappeared in an Array
-
LeetCode-448. Find All Numbers Disappeared in an Array
-
Leetcode 448. Find All Numbers Disappeared in an Array (python+cpp)
-
LeetCode之Find All Duplicates in an Array
-
Leetcode No.26 Remove Duplicates from Sorted Array(c++实现)
-
【LeetCode】80. Remove Duplicates from Sorted Array II (删除排序数组中的重复项 II)-C++实现及详细图解
-
【LeetCode】26. Remove Duplicates from Sorted Array (删除排序数组中的重复项)-C++实现的两种方法