leetcode array|442. Find All Duplicates in an Array

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]

---

本道题目与之前做的寻找数组中未出现过的元素的题目很相似，要求找出出现两次的数字。

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

模仿其取负法，思路为第一次出现取负，第二次出现将此数乘n+1，再遍历一次数组，比n大的元素为出现两次的元素。

但是当数组内元素过大时会出现溢出！！！

///这是错误的代码，会溢出！！！
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        //在找没有出现过的情况的时候使用取负法
        List<Integer> ans=new ArrayList<>();
        int n=nums.length;
        for(int i=0;i<n;i++){
            int index;
            if(nums[i]>=-n&&nums[i]<=n){
                index=Math.abs(nums[i])-1;
            }
            else{
                index=Math.abs(nums[i])/(n+1)-1;
            }
            if(nums[index]>0&&nums[index]<=n){
                nums[index]=-nums[index];
            }
            else if(nums[index]>=-n&&nums[index]<0){
                nums[index]=nums[index]*(n+1);
            }
        }
        for(int i=0;i<n;i++){
            if(-nums[i]>n){
                ans.add(i+1);
            }
        }
        return ans;
    }
}

换了一种思路，不乘了，我减，如果是第二次遍历到这个元素的话就再减去（n-1），其他条件不变，运行之后居然没有溢出？？？那要是元素只比最大的数小一咋办，不是照样溢出嘛？？？

但是相对乘法而言，也是改善了很多，计算所花的时间也更少。

悄咪咪抖机灵，要是用python写的话，是不是直接乘也不会溢出，嘿嘿嘿

///代码运行通过
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        //在找没有出现过的情况的时候使用取负法
        List<Integer> ans=new ArrayList<>();
        int n=nums.length;
        for(int i=0;i<n;i++){
            int index;
            if(nums[i]>=-n&&nums[i]<=n){
                index=Math.abs(nums[i])-1;
            }
            else{
                index=Math.abs(nums[i])-(n+1)-1;
            }
            if(nums[index]>0&&nums[index]<=n){
                nums[index]=-nums[index];
            }
            else if(nums[index]>=-n&&nums[index]<0){
                nums[index]=nums[index]-(n+1);
            }
        }
        for(int i=0;i<n;i++){
            if(-nums[i]>n){
                ans.add(i+1);
            }
        }
        return ans;
    }
}