leetcode 448题

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

思路

要保证在 O(N) 的复杂度实现，那么只能用一层循环，标记已经出现的数字

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function findDisappearedNumbers(nums) {
    const res = [];
    
    for (let v of nums){
        if (v < 0) {
            v = -v;
        }
        if (nums[v - 1] > 0) {
            nums[v - 1] = -nums[v - 1];
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            res.push(i+1);
        }
    }

    return res;
}

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

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

思路

代码

CATALOG

FEATURED TAGS

FRIENDS