448. 找到所有数组中消失的数字

小咪咪 2022-12-02 01:11 195阅读 0赞

# 题目： #

[448. 找到所有数组中消失的数字][448.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

## 1. 题解一：使用哈希表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]

## 2. 题解二：原地修改（首选） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]

/** * * 找出 1 - n 中没有出现的数字。不能使用额外的空间，两次循环时间复杂度为 2O(n)，即为 O(n)。 * * 解题思路：使用数组的下标来标记数字的出现于否，通过一遍遍历即可标记出全部已经出现的数组 * * [4,3,2,7,8,2,3,1] 初始数据 * * [4,3,2,-7,8,2,3,1] 第一个数据 4 出现，将数组的第四个也就是下标 3 的数据修改为负数。-7 计算时，通过绝对值处理一下即可不影响数据的计算 * [4,3,-2,-7,8,2,3,1] * [4,-3,-2,-7,8,2,3,1] * [4,-3,-2,-7,8,2,-3,1] * [4,-3,-2,-7,8,2,-3,-1] * [4,-3,-2,-7,8,2,-3,-1] * [4,-3,-2,-7,8,2,-3,-1] * [-4,-3,-2,-7,8,2,-3,-1] * * 计算结束，数组的第五个，第六个依然为整数，证明 5,6 没有出现 * * @param nums * @return */

# 代码： #

## 1. 代码一：使用哈希表 ##

import java.util.*;
    
    public class code448 { 
    
        // 方法一: 使用哈希表
        public static List<Integer> findDisappearedNumbers(int[] nums) { 
            List<Integer> res = new ArrayList<>();
    
            HashMap<Integer, Integer> map = new HashMap<>();
    
            for(int i = 0; i < nums.length; i++)
            { 
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
    
            for(int i = 1; i <= nums.length; i++)
            { 
                if(map.get(i) == null)
                { 
                    res.add(i);
                }
            }
    
            return res;
        }
    
        public static void main(String[] args) { 
            int nums[] = {  4, 3, 2, 7, 8, 2, 3, 1 };
            List<Integer> res = findDisappearedNumbers(nums);
            System.out.println(res.toString());
        }
    }

## 2. 代码二：原地修改（首选） ##

import java.util.*;
    
    public class code448 { 
    
        // 方法二: 原地修改
        public static List<Integer> findDisappearedNumbers(int[] nums) { 
            // 初始化结果列表
            List<Integer> res = new ArrayList<>();
    
            // 第一遍扫描，根据数组的值找到对应的下标，比如 3 对应下标 2,将 arr[2] 设置成负数
            // 遍历数组,将 nums[i] - 1 索引位置的元素标记为负数
            for(int i = 0; i < nums.length; i++)
            { 
                // 先获取当前元素的绝对值,然后 -1 进而将当前元素转换为 nums 数组的索引值
                int index = Math.abs(nums[i]) - 1;
                // 若该索引值在数组 nums 中存在,则将其所指的元素变为负数
                if(nums[index] > 0)
                { 
                    nums[index] = nums[index] * (-1);
                }
            }
    
            // 第二遍扫描，找到所有非负数，非负数所在的下标+1，即为缺失的数字
            // 再次遍历数组,若当前数组元素 nums[i] 为负数,则说明在数组中存在数字: i + 1
            // 反之则说明数组中缺失的数字为: i + 1
            for(int i = 0; i < nums.length; i++)
            { 
                // 将缺失的数字添加到结果列表中
                if(nums[i] > 0)
                { 
                    res.add(i + 1);
                }
            }
            // 返回结果列表
            return res;
        }
    
        public static void main(String[] args) { 
            int nums[] = {  4, 3, 2, 7, 8, 2, 3, 1 };
            List<Integer> res = findDisappearedNumbers(nums);
            System.out.println(res.toString());
        }
    }

# 参考： #

1.  [找到所有数组中消失的数字][Link 1]
2.  [C++，原数组操作][C]
3.  [多图演示 448.找到所有数组中消失的数字][448. 1]
4.  [抽屉原理 + 基于“异或运算”交换两个变量的值（Python 代码、Java 代码）][_ _Python _Java]

[448.]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/562641c4a5164ff6bfdffa10a55fdadb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/94fff896e9914952a4d787c59bc6a958.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/d2b9e4d1a27c4b76aa508e64e2a939d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/7be4627690134b41b108f8ddbc62f488.png
[Link 1]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/zhao-dao-suo-you-shu-zu-zhong-xiao-shi-de-shu-zi-2/
[C]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/cyuan-shu-zu-cao-zuo-by-haydenmiao/
[448. 1]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/duo-tu-yan-shi-448zhao-dao-suo-you-shu-zu-zhong-xi/
[_ _Python _Java]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/solution/tong-pai-xu-ji-yu-yi-huo-yun-suan-jiao-huan-liang-/