leetcode41-缺失的第一个正数
第一个 缺失 正数
2023-09-27 14:27:45 时间
题目:给定一个未排序的整数数组,找出其中没有出现的最小的正整数。要求时间复杂度O(n)、空间复杂度O(1)
分析:
首先想到用个vis数组,数组开多大呢,需要根据数的范围(其实只需要开n的大小,因为我们不需要关心小于1和大于n的数)
但是这样需要额外的空间,不符合题意。于是想着能不能将原数组当作vis数组用,用取反(负数)作为“出现过”的标记。
整理一下:
1. 遍历一篇看是否有1,没有直接return 1
2. 将在[1, n]之外的置为1
3. 遍历,将每个值(取绝对值,因为可以被取负了)作为索引的位置取反(如果之前是正数的话)
4. 遍历一遍,第一个非负数的索引即答案。
class Solution { public: int firstMissingPositive(vector<int>& a) { int n = a.size(); int flag = false; for(int i = 0;i < n;i++) if(a[i] == 1) { flag = true; break; } if(!flag) return 1; for(int i = 0;i < n;i++) // 小于1,大于n的都改成1 { if(a[i] <= 0) a[i] = 1; if(a[i] > n) a[i] = 1; } for(int i = 0;i < n;i++) { int index = a[i]-1; if(a[i] < 0) index = -a[i]-1; if(a[index] > 0) a[index] = - a[index]; } int ans = n+1; for(int i = 0;i < n;i++) if(a[i] > 0) { ans = i+1; break; } return ans; } };
相关文章
- leetCode 41.First Missing Positive (第一个丢失的正数) 解题思路和方法
- 手把手教你在 CoreOS 上构建你的第一个应用
- 《Java编码指南:编写安全可靠程序的75条建议(英文版)》—— 第2章 编写第一个程序 2.1 编写程序所需的工具
- Flutter新手第一个坑:Could not find com.android.tools.lint:lint-gradle:26.1.1.
- 《OpenGL ES应用开发实践指南:Android卷》—— 1.2 创建第一个程序
- 第一个go的web程序;调用七牛云存储的音频api问题解决;条件搜寻文件中的内容,字符串拼接+在上一行
- C++ 之 Windows Visual Studio 开发环境搭建/C++第一个Hello World
- 【MyBatis】第一个案例
- 【历史上的今天】11 月 21 日:第一个阿帕网连接建立;乐视网成立;爱迪生发明留声机
- FusionCharts简单教程(一)---建立第一个FusionCharts图形
- 从零学Java(3)之第一个实例HelloWorld
- Vue开发实例(01)之环境搭建nodejs与运行第一个Vue项目