leetcode 442. Find All Duplicates in an Array

小咪咪 2022-06-13 00:56 283阅读 0赞

1.题目

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.
给一个数组，数组元素在范围[1,n]，n是数组长度。其中，有些数字出现两次，有些数字只出现一次。
找出出现两次的元素，不开辟额外空间，时间复杂度O(n)
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]

2.分析

找出出现两次的元素，复杂度O(n)，数组遍历一遍。
由于元素大小在范围[1,n]，数组下标范围[0,n-1]刚好对应。
对于已经出现的元素x，A[x-1] 为 -A[x-1]。下次再标记时发现已经为负数则表示该数字已经出现过。

3.代码

  1. class Solution {
  2. public:
  3.     vector<int> findDuplicates(vector<int>& nums) {
  4.         vector<int> ans;
  5.         for (int x : nums) {
  6.             x = abs(x);
  7.             if (nums[x - 1] < 0)
  8.                 ans.push_back(x);
  9.             else
  10.                 nums[x - 1] *= -1;
  11.         }
  12.         return ans;
  13.     }
  14. };

发表评论

表情：
评论列表 （有 0 条评论，283人围观）

还没有评论，来说两句吧...

相关阅读