leetcode Set

leetcode 41题

Posted by franki on June 11, 2021

leetcode 41题 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例1

输入：nums = [1,2,0]
输出：3

示例2

输入：nums = [3,4,-1,1]
输出：2

示例3

输入：nums = [7,8,9,11,12]
输出：1

思路

通过 set 先记录出现的数字，接着从1到nums.length+1依次遍历，假如当前下标不在 set 里面，说明该下标就是缺失的整数，若遍历完成全部都在 set 里面，那么缺失的数字就是 nums.length + 1。

代码

var firstMissingPositive = function(nums) {
    const set = new Set();
    for (let i=0; i<nums.length; i++) {
        set.add(nums[i]);
    }
    for (let i=1; i<nums.length+1; i++) {
        if (!set.has(i)) {
            return i;
        }
    }
    return nums.length+1;
};

复杂度分析:

  • 时间复杂度: O(N)
  • 空间复杂度：O(N)
CATALOG
    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 SVG
    FRIENDS