C++实现LeetCode(41.首个缺失的正数)

[LeetCode] 41. First Missing Positive 首个缺失的正数

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

这道题让我们找缺失的首个正数,由于限定了 O(n) 的时间,所以一般的排序方法都不能用,最开始博主没有看到还限制了空间复杂度,所以想到了用 HashSet 来解,这个思路很简单,把所有的数都存入 HashSet 中,然后循环从1开始递增找数字,哪个数字找不到就返回哪个数字,如果一直找到了最大的数字(这里是 nums 数组的长度),则加1后返回结果 res,参见代码如下:

解法一:

// NOT constant space
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int res = 1, n = nums.size();
        while (res <= n) {
            if (!st.count(res)) return res;
            ++res;
        }
        return res;
    }
};

但是上面的解法不是 O(1) 的空间复杂度,所以需要另想一种解法,既然不能建立新的数组,那么只能覆盖原有数组,思路是把1放在数组第一个位置 nums[0],2放在第二个位置 nums[1],即需要把 nums[i] 放在 nums[nums[i] - 1]上,遍历整个数组,如果 nums[i] != i + 1, 而 nums[i] 为整数且不大于n,另外 nums[i] 不等于 nums[nums[i] - 1] 的话,将两者位置调换,如果不满足上述条件直接跳过,最后再遍历一遍数组,如果对应位置上的数不正确则返回正确的数,参见代码如下:

解法二:

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

到此这篇关于C++实现LeetCode(41.首个缺失的正数)的文章就介绍到这了,更多相关C++实现首个缺失的正数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(94.二叉树的中序遍历)

    [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively

  • C++实现LeetCode(78.子集合)

    [LeetCode] 78. Subsets 子集合 Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is:

  • C++实现LeetCode(112.二叉树的路径和)

    [LeetCode] 112. Path Sum 二叉树的路径和 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below bi

  • C++实现LeetCode(47.全排列之二)

    [LeetCode] 47. Permutations II 全排列之二 Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 这道题是之前那道 Permutations 的延伸,由于输入数组有可能出现重复数字,如果按照之前的

  • C++实现LeetCode(90.子集合之二)

    [LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example

  • C++实现LeetCode(144.二叉树的先序遍历)

    [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input:  [1,null,2,3] 1 \ 2 / 3 Output:  [1,2,3] Follow up: Recursive solution is trivial, could you do it iterat

  • C++实现LeetCode(40.组合之和之二)

    [LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u

  • C++实现LeetCode(41.首个缺失的正数)

    [LeetCode] 41. First Missing Positive 首个缺失的正数 Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your

  • C++实现LeetCode(163.缺失区间)

    [LeetCode] 163. Missing Ranges 缺失区间 Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges. Example: Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99, Output: ["2&q

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • JS实现扫码枪扫描二维码功能

    扫码枪扫描二维码,具体内容如下所示: 业务需求要将数据生成二维码,并用扫码枪扫出数据上传到服务端. 先上代码吧,之后再完善注意点 this.start = new Date().getTime() let code = '' let lastTime, nextTime let lastCode, nextCode let that = this window.document.onkeypress = function (e) { if (window.event) { // IE nextC

  • js 获取扫码枪输入数据的方法

    1.扫码枪相当于键盘输入设备,输入一连串数字后加一个enter键.但在实际开发中需要区分是扫描枪输入还是键盘用户输入,区别在于扫码枪输入很快. let code = ''; let lastTime, nextTime; let lastCode, nextCode; window.document.onkeypress = (e) => { if (window.event) { // IE nextCode = e.keyCode; } else if (e.which) { // Nets

  • js获取USB扫码枪数据的方法

    本文实例为大家分享了js获取USB扫码枪数据的具体过程,供大家参考,具体内容如下 废话不多说,直接上代码,这个方法避免了 首字缺失,字符串乱码等等问题,特别好用,记录一下 中间的Ajax可直接调用登录功能,实现自动登录 说明:输入框需要获得焦点,这个是必须的,其次为了防止回车触发手动登录,需要添加οnkeypress="if(event.keyCode==13) return false;"这个操作,这个在回车的时候,输入框焦点不会丢失,除非手动切换焦点,或者调用focus();方法

  • Python 3.10 的首个 PEP 诞生,内置类型 zip() 迎来新特性(推荐)

    译者前言:相信凡是用过 zip() 内置函数的人,都会赞同它很有用,但是,它的最大问题是可能会产生出非预期的结果.PEP-618 提出给它增加一个参数,可以有效地解决大家的痛点. 这是 Python 3.10 版本正式采纳的第一个 PEP,「Python猫」一直有跟进社区最新动态的习惯,所以翻译了出来给大家尝鲜,强烈推荐一读.(PS:严格来说,zip() 是一个内置类(built-in type),而不是一个内置函数(built-in function),但我们一般都称它为一个内置函数.) PE

  • 有关IntelliJ IDEA中LeetCode插件配置问题

    最初目的是在实验室电脑和笔记本电脑上同时配置好这个刷题插件,并且Git互联,并锻炼自己debug以及输入输出. 前面的可以参考教程:安装 首先是在IntelliJ上面下载安装好LeetCode插件, 然后配置好登录名和密码, 一切都很顺利,按照网上的教程走的很顺利. 然后我的配置模板是: 标题: P$!{question.frontendQuestionId}_$!velocityTool.camelCaseName(${question.titleSlug}) 代码模板: ${question

  • C++实现LeetCode(6.字型转换字符串)

    [LeetCode] 6. ZigZag Conversion 之字型转换字符串 The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P   A   H   N A P L S I I G Y  

  • C++实现LeetCode(验证数字)

    [LeetCode] Valid Number 验证数字 Validate if a given string can be interpreted as a decimal number. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true "

随机推荐