448. Find All Numbers Disappeared in an Array

查找缺失的数据

相似的题目查看如下链接的基本情况

448 查找缺失的数据

442. Find All Duplicates in an Array

先解决查找数组当中相同的元素

这道题目是442的，如何查找出数组当中出现多次的元素， 这就是桶排序算法

数组当中的每个元素大小都是1<<x<<n ，

只要注意这两个地方即可

1. 桶排序，归位处理
2. 遍历一遍， 将没有归位处理的元素进行添加操作即
   注意上面归位的意思是指元素的再相应的位置上面即可，所以在这里的是跟坐标的元素进行对比即可

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        // 桶排序算法， 归位处理即可
        List<Integer> result= new LinkedList<>();
        if(nums==null || nums.length==0)
            return result;
        for( int i=0;i<nums.length;i++){
            // 进行一定的元素交换的基本情况     
        // 判断是否数组越界的问题， 不断进行处理该种情况即可
        while(nums[i]!=nums[nums[i]-1])
            {
                int tmp = nums[i];
                nums[i]= nums[nums[i]-1];
                nums[nums[i]-1] =tmp;
            }
        }
        for(int i=0;i<nums.length;i++){
            //判断是否还有还有没有归位处理的元素情况
            if(i=nums[i]-1)
                result.add(nums[i]);
        }
        return result;
    }
}

如果是查找不存在的元素类似448题目， 就是讲左边相加的元素进行添加

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
           List<Integer> result= new LinkedList<>();
        if(nums==null || nums.length==0)
            return result;
        // 判断是否数组越界的问题， 不断进行处理该种情况即可
         for(int i=0;i< nums.length;i++){
         while(nums[i]!=nums[nums[i]-1])
            {
                int tmp = nums[nums[i]-1];
                nums[nums[i]-1]= nums[i];
                nums[i] =tmp;
            }
        }
         for(int i=0;i< nums.length;i++){
                if(i!=nums[i]-1){
                // 把相同元素的添加到中间即可
                    result.add(i+1);
                }
        }
    return result;
    }
}

标记方法

比如数组Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

假如 1出现了在数组当中， 我们将数组当中的int array[1]= 变换 为 求相反数， 即可，
变成
[-4,3,2,7,8,2,3,1], array[1]<0 所以index =1 肯定是出现在了数组当中
比如5 没出现在数组当中， 所以array[5] = 8 还是大于0， 在这种情况下

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
           List<Integer> result= new LinkedList<>();
        if(nums==null || nums.length==0)
            return result;
        // 判断是否数组越界的问题， 不断进行处理该种情况即可
         for(int i=0;i< nums.length;i++){
        // 每个数组当中数据对应的是下标元素
             int index = Math.abs(nums[i])-1;
             if(nums[index]>0){
                 nums[index]= -nums[index];
             }
        
        }
         for(){
                if(nums[i]>0){
                    result.add(i+1);
                }
        }
    return result;
    }
}