【技巧模版】数组原地修改的专栏训练（java版本含注释）

• 前言
• 442. 数组中重复的数据（中等）
• 448. 找到所有数组中消失的数字（简单）
• 剑指 Offer 03. 数组中重复的数字（简单）

一般这种题型多数为数组
输出数组出现2个的个数
输出数组不是1到n的个数等等题型
一般可以使用map集合，但是复杂度偏高
是否可使用其他方式进行优化呢

进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

题目：leetcode：442. 数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[2,3]

示例 2：

输入：nums = [1,1,2]
输出：[1]

示例 3：

输入：nums = [1]
输出：[]

提示：

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= n
nums 中的每个元素出现 一次 或 两次

class Solution {
    public List findDuplicates(int[] nums) {
        Listlist = new ArrayList<>();
        
        
        
        for(int i = 0;i < nums.length;i++){
            int ans = Math.abs(nums[i]);
            if(nums[ans-1] < 0)list.add(ans);
            else nums[ans-1] *=-1;
        }
        
        return list;

        
    }
}

除了取反还有增加偏移量的操作
具体可看该题解：【负雪明烛】动画题解，原地修改数组，通俗易懂

或者使用原地转换判定，通过数组下标与对应值进行映射

class Solution {
    public List findDuplicates(int[] nums) {
        Listlist =new ArrayList<>();
        for(int i=0;i
            //第一个i放在合适的位置，满足的第二个i放在不冲突的位置上
            while(nums[i]!=nums[nums[i]-1]){
                
                swap(nums,i,nums[i]-1);
            }
        }

        for(int i=0;i
            if(nums[i]-1!=i)list.add(nums[i]);
        }
        return list;
        
    }

    public void swap(int []nums,int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }
    
}

题目：leetcode：448. 找到所有数组中消失的数字

大致意思如下：
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

提示：

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        Listlist =new ArrayList<>();
        for(int i=0;i
            while(nums[i]!=nums[nums[i]-1]){
                swap(nums,i,nums[i]-1);
            }
        }

        for(int i=0;i
            

            if(nums[i]-1!=i)list.add(i+1);
        }

        return list;

        
    }

    //此处为置换排序，根本的思想其实就是nums[nums[i]]==nums[i]
    public void swap(int []nums,int a,int b){
            int temp=nums[a];
            nums[a]=nums[b];
            nums[b]=temp;
    }
        
    
}

使用取反的操作，具体代码如下：

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        Listlist =new ArrayList<>();
        for(int i=0;i
            int ans=Math.abs(nums[i]);
            if(nums[ans-1]>0)nums[ans-1] *=-1;
        }

        for(int i=0;i
            if(nums[i]>0)list.add(i+1);
        }

        return list;


    }
    
}

题目：leetcode：剑指 Offer 03. 数组中重复的数字

大致意思如下：

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

class Solution {
    public int findRepeatNumber(int[] nums) {

        for(int i=0;i
            //本身数组的下标和 对应的值 都是0到n-1.
            while(nums[i]!=nums[nums[i]]){
                swap(nums,i,nums[i]);
            }
        }

        for(int i=0;i
            if(nums[i]!=i)return nums[i];
        }

        return -1;

        
    }
//此处为置换排序，根本的思想其实就是nums[nums[i]]==nums[i]
    public void swap(int []nums,int a,int b){
            int temp=nums[a];
            nums[a]=nums[b];
            nums[b]=temp;
    }
}