442. Find All Duplicates in an Array 找数组中重复的数

本文主要是介绍442. Find All Duplicates in an Array 找数组中重复的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/description/
题意：找出数组中所有重复的元素

思路1:先将数组排序,然后判断是否重复,即若nums[i] != nums[i+1],即说明nums[i]非重复元素,可以删去.
重点在于指针(迭代器)的操作,由于vector的erase(删除)操作需要通过迭代器进行,而且删除元素后,右侧的元素全部左移一格,这就导致一开始写的时候总是找不到bug所在.

例如排序后的

1 2 2 3 3 4 5 6 7 8

得到却是

2 3 4 6 8

为何非重复的4,6都没删呢?就是因为erase第二个3之后,it实际上已经指向4,此时再it++,就指向5了.同理6也这样被跳过.

此外还有最后一位元素,若是重复的,直接pop掉即可,若是非重复的,也可以pop掉,所以it只遍历到end-1,最后整个数组pop_back()即可.

vector<int> findDuplicates(vector<int>& nums) {sort(nums.begin(), nums.end()); //先排序vector<int>::iterator it = nums.begin();while (it != nums.end()-1) {if (*it != *(it+1)) nums.erase(it); //找到则删除else it++;  //找不到则指针后移}nums.pop_back();return nums;
}

改进：借鉴26. Remove Duplicates from Sorted Array
的思路。实际上不用这么麻烦，没必要删除。用两个指针i，j即可。先对整个数组排序，i初始为0，表示无重复部分，j从1开始向后遍历整个数组，若找到与i相等的元素，记录在res中，i不动，j继续向前。若j找到与i不想等的元素，则无重复部分增长1（i加1），并将j处元素写入i。最后返回res

class Solution:def findDuplicates(self, nums):""":type nums: List[int]:rtype: List[int]"""res = []n = len(nums)if n == 0:return resnums.sort()i = 0j = 1while j < n:if nums[j] == nums[i]:res.append(nums[i])j += 1else:nums[i+1] = nums[j]i += 1j += 1return res

思路2(借鉴别人的,非常巧妙):
由于数字范围与数组长度有关(1 ≤ a[i] ≤ n ),因此可以将元素值与元素下标联系起来(由于下标范围是0~n-1,因此还需要做一个偏移).从头遍历数组nums,将元素值作为下标(index)访问数组相应位置,然后置为相反数,若这个位置nums[index]被访问过,则<0,这样就知道重复了两次.

vector<int> findDuplicates(vector<int>& nums) {vector<int> res;for (int i = 0; i < nums.size(); i++) {int index = abs(nums[i]) - 1; // 数组元素值映射为下标if (nums[index] < 0) { // 若<0,说明之前访问过,这是第二次访问res.push_back(index+1); // 这个位置符合}nums[index] = -nums[index]; // 置为相反数}return res;}

py:

class Solution:def findDuplicates(self, nums):""":type nums: List[int]:rtype: List[int]"""res = []for i in range(len(nums)):index = abs(nums[i]) - 1if nums[index] < 0:res.append(index+1)            nums[index] = -nums[index]return res