文档章节

代码题(40)— 缺失的第一个正数、缺失数字

o
 osc_4nmshwhm
发布于 2018/08/08 09:51
字数 590
阅读 9
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

1、41. 缺失的第一个正数

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

示例 1:

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

示例 2:

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

示例 3:

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

思路:交换数组元素。使得数组中第i位存放数值(i+1)。

最后遍历数组,寻找第一个不符合此要求的元素,返回其下标。整个过程须要遍历两次数组,复杂度为O(n)。

下图以题目中给出的第二个样例为例,解说操作过程。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty())
            return 1;
        int n = nums.size();

        for(int i=0;i<n;++i)
        {
            if(nums[i] <= 0)
                continue;
            //思路:交换数组元素。使得数组中第i位存放数值(i+1)。
            //假设交换的数据还是大于0且<i+1,且数据不相等,则放在合适的位置,避免死循环
            while(nums[i]>0 && nums[i]<=i+1 && nums[i] != nums[nums[i]-1])
                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;
    }
};

 

2、268. 缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

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

示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

  这道题还可以用二分查找法来做,我们首先要对数组排序,然后我们用二分查找法算出中间元素的下标,然后用元素值和下标值之间做对比,如果元素值大于下标值,则说明缺失的数字在左边,此时将right赋为mid,反之则将left赋为mid+1。那么看到这里,作为读者的你可能会提出,排序的时间复杂度都不止O(n),何必要多此一举用二分查找,还不如用上面两种方法呢。对,你说的没错,但是在面试的时候,有可能人家给你的数组就是排好序的,那么此时用二分查找法肯定要优于上面两种方法。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if(nums.empty())
            return -1;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        
        int left = 0,right = n;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(nums[mid] == mid)
                left = mid+1;
            else 
                right = mid;
        }
        return right;
    }
};

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【每日算法Day 75】字节跳动面试题:手撕困难题,看过我Day 71的人都会做了!

题目链接 LeetCode 41. 缺失的第一个正数[1] 题目描述 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 示例1 示例2 示例3 说明: 题解 如果之前一直坚持看我题解的同学,应该前...

godweiyang
03/20
1
0
LeetCode 41. 缺失的第一个正数 | Python

缺失的第一个正数 题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/first-missing-positive 题目 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 示...

大梦三千秋
06/27
2
0
LeetCode(41):缺失的第一个正数

Hard! 题目描述: 给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0]输出: 3 示例 2: 输入: [3,4,-1,1]输出: 2 示例 3: 输入: [7,8,9,11,12]输出: 1 说明...

osc_lmwjsnx3
2018/06/05
1
0
Leetcode 30-50题总结

LeetCode 31. 下一个排列 排列数规律,难 LeetCode 32. 最长有效括号 难 LeetCode 33. 搜索旋转排序数组 两次二分,第一次先找到旋转位置,第二次再有序数组里找,将两次二分合并成一个。 Le...

osc_8r37p3dx
06/19
6
0
【剑指offer】(第 2 版)Java 题解

【剑指offer】(第 2 版)Java 题解 第一章 面试的流程 略... 第二章 面试需要的基础知识 ###面试题 1. 赋值运算符函数 面试题 2. 实现 Singleton 模式 Solution 2 面试题 3. 数组中重复的数...

osc_4bfj636c
2018/08/28
6
0

没有更多内容

加载失败,请刷新页面

加载更多

未捕获ReferenceError:未定义$? - Uncaught ReferenceError: $ is not defined?

问题: How come this code throws an 此代码如何引发 Uncaught ReferenceError: $ is not defined 未捕获的ReferenceError:未定义$ when it was OK before? 以前什么时候可以? $(document......

javail
34分钟前
12
0
263. Ugly Number

题目: 263. Ugly Number 题目地址:https://leetcode.com/problems/ugly-number/ Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers......

JiaMing
57分钟前
60
0
HCIA_ARP01

ARP(地址解析协议) eNSP 常用路由器:AR2220 常用交换机:S5700、S3700 常用终端:PC、MCS(主播服务器) 设备连线:Copper(以太网用到的双绞线)、Serial(串口线,2SA接口)、Auto(自动连...

创业789
今天
25
0
如何在Rails 4中使用问题 - How to use concerns in Rails 4

问题: The default Rails 4 project generator now creates the directory "concerns" under controllers and models. 默认的Rails 4项目生成器现在在控制器和模型下创建目录“Concer”。 ......

fyin1314
今天
19
0
【LeetCode】 57 括号生成

题目: 解题思路: https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/ 代码: import java.util.ArrayList;import java.util.List;publ......

JaneRoad
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部