LeetCode-442. Find All Duplicates in an ArrayLevel up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.https://leetcode.com/problems/find-all-duplicates-in-an-array/
题目描述Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.
You must write an algorithm that runs in O(n) time and uses only constant extra space.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]
Example 2:
Input: nums = [1,1,2] Output: [1]
Example 3:
Input: nums = [1] Output: []
Constraints:
n == nums.length1 <= n <= 1051 <= nums[i] <= nEach element in nums appears once or twice.
解题思路 【C++解法】 1、负负得正class Solution {
public:
vector findDuplicates(vector& nums) {
// negate all values
for (int i=0; i two time repeated will get positive and missing will remain negative(from first pass)
for (int i=0; isol;
for (int i=0; i0) {sol.push_back(i+1);}}
return sol;
}
};
2、交换排序
class Solution {
public:
vector findDuplicates(vector& nums) {
int i = 0, n = nums.size();
while(i < n){
if(nums[i] != nums[nums[i]-1]) swap(nums[i], nums[nums[i]-1]);
else i++;
}
vector res;
for(i=0; i
3、哈希标记
class Solution {
public:
vector findDuplicates(vector& nums) {
vectorres;
int i = 0;
for(int i=0; i
【Java解法】
1、负负得正
class Solution {
public List findDuplicates(int[] nums) {
List res = new ArrayList();
for (int i=0; i0) {res.add(i+1);}}
return res;
}
}
2、交换排序
class Solution {
public List findDuplicates(int[] nums) {
List res = new ArrayList();
int i = 0, n = nums.length;
while(i < n){
if(nums[i] != nums[nums[i]-1]) {nums = swap(nums, i, nums[i]-1);}
else i++;
}
for(i=0; i
3、哈希标记
class Solution {
public List findDuplicates(int[] nums) {
List res = new ArrayList();
for(int i=0; i
参考文献
【1】Java中List集合的常用方法 - xiaostudy - 博客园
