专栏首页算法码上来【每日算法Day 75】字节跳动面试题:手撕困难题,看过我Day 71的人都会做了!

【每日算法Day 75】字节跳动面试题:手撕困难题,看过我Day 71的人都会做了!

题目链接

LeetCode 41. 缺失的第一个正数[1]

题目描述

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例1

输入:
[1,2,0]
输出:
3

示例2

输入:
[3,4,-1,1]
输出:
2

示例3

输入:
[7,8,9,11,12]
输出:
1

说明:

  • 你的算法的时间复杂度应为 ,并且只能使用常数级别的空间。

题解

如果之前一直坚持看我题解的同学,应该前几天刚看过下面这道题:

【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法

韦阳的博客:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法[2]

知乎专栏:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法[3]

那道题是要求 到 中缺失的两个数,于是我们开辟一个大小为 的数组,将所有数字放到下标对应的位置,然后看哪两个位置是空着的。为了使用原地算法,我们直接在原数组上进行操作。

回到本题,我们要寻找的是第一个缺失的正整数。其实问题的本质是一样的,如果数组的长度是 ,那么最多只能填充 到 这 个正整数,所以缺失的正整数一定小于等于 。

那么我们把小于等于 或者大于 的数全部赋值为 ,因为它们是多少不要紧,不影响最后的结果。然后和上面题目方法一样,用原地算法,把每个数字放入对应下标的位置。最后从左到右扫描一遍数组,如果发现有位置是 ,那么第一个缺失的正数就是它了。如果扫描完 到 发现全都在,那么第一个缺失的就是 了。当然可能缺失很多正数,所以扫描到第一个缺失正数之后,就要直接返回结果了。

因为我们要保存 到 之间的数,所以数组长度不够,要在后面扩充一个才行。

时间复杂度是 ,空间复杂度是 。

代码

c++

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

参考资料

[1]

LeetCode 41. 缺失的第一个正数: https://leetcode-cn.com/problems/first-missing-positive/

[2]

韦阳的博客:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法: https://godweiyang.com/2020/03/16/leetcode-interview-17-19/

[3]

知乎专栏:【每日算法Day 71】面试官想考我这道位运算题,结果我给出了三种解法: https://zhuanlan.zhihu.com/p/113534188

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~

本文分享自微信公众号 - 算法码上来(GodNLP),作者:godweiyang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【每日算法Day 82】面试经典题:求第K大数,我写了11种实现,不来看看吗?

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    godweiyang
  • 每日算法系列【LeetCode 153】寻找旋转排序数组中的最小值

    (例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2])。

    godweiyang
  • 每日算法系列【LeetCode 330】按要求补齐数组

    给定一个已排序的正整数数组 nums ,和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中,使得 [1, n] 区间内的任何数字都可...

    godweiyang
  • LeetCode 1464. 数组中两元素的最大乘积

    给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-1) 取得最大值。

    Michael阿明
  • LeetCode 16 3Sum Closest

    ShenduCC
  • Leetcode 628. 三个数的最大乘积 (数学)

    解题思路 方法一:排序 我们将数组进行升序排序,如果数组中所有的元素都是非负数,那么答案即为最后三个元素的乘积。

    glm233
  • Leetcode 15 三数之和(双指针,去重)

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    glm233
  • Q189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

    echobingo
  • Array - 508. Wiggle Sort

    Given an unsorted array nums, reorder it in-place such that

    用户5705150
  • 【剑指Offer】调整数组顺序使奇数位于偶数前面

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

    小新哟

扫码关注云+社区

领取腾讯云代金券