leetcode 448. 找到所有数组中消失的数字（Java版）

系统管理员 2023-01-17 09:27 126阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/][https_leetcode-cn.com_problems_find-all-numbers-disappeared-in-an-array]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 思路 ##

维护一个 bool 数组，用来记录哪些数字出现过。最后遍历这个 bool 数组，将没有出现过的数字 append 进用于返回的 list 中。

## 代码 ##

import java.util.ArrayList;
    import java.util.List;
    
    public class Solution { 
        public List<Integer> findDisappearedNumbers(int[] nums) { 
            List<Integer> result = new ArrayList<>();
            boolean[] hasNums = new boolean[nums.length + 1];
            for (int n : nums) { 
                hasNums[n] = true;
            }
            for (int i = 1; i < nums.length + 1; i++) { 
                if (!hasNums[i]) result.add(i);
            }
            return result;
        }
    }

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

## 其他解法 ##

不使用额外空间的方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

class Solution { 
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) { 
            int n = nums.size();
            for (auto& num : nums) { 
                int x = (num - 1) % n;
                nums[x] += n;
            }
            vector<int> ret;
            for (int i = 0; i < n; i++) { 
                if (nums[i] <= n) { 
                    ret.push_back(i + 1);
                }
            }
            return ret;
        }
    };

**复杂度分析**

时间复杂度：O(n)。其中 n 是数组 nums 的长度。

空间复杂度：O(1)。返回值不计入空间复杂度。

[https_leetcode-cn.com_problems_find-all-numbers-disappeared-in-an-array]: https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221021/fdf831db474347dd8c141fa5e930823d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221021/825b7ddf188443e4b0bb664a660f6d87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221021/dba4275a22e0446ea4641a4ed32ae5ad.png