LeetCode448——找到所有数组中消失的数字

素颜马尾好姑娘i 2022-04-25 08:32 196阅读 0赞

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCode]

原题链接：[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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70][]

知识点：数组

### 思路：与[LeetCode041——缺失的第一个正数][LeetCode041]同样的思路 ###

核心原则就是重构原数组，使得索引为i的位置放置的元素是i + 1。

时间复杂度是O(n)。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    
        public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                    swap(nums, i, nums[i] - 1);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != i + 1) {
                    result.add(i + 1);
                }
            }
            return result;
        }
    
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    
    }

LeetCode解题报告：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1][]

[https_github.com_617076674_LeetCode]: https://github.com/617076674/LeetCode
[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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70]: /images/20220125/a224850be17a43cf9069121de196699b.png
[LeetCode041]: https://blog.csdn.net/qq_41231926/article/details/82656191
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjMxOTI2_size_16_color_FFFFFF_t_70 1]: /images/20220125/d16c7410b72243c7bd8a01f8b6f5dfb7.png