当前位置:网站首页>LeetCode:41. 缺失的第一个正数
LeetCode:41. 缺失的第一个正数
2022-07-06 08:44:00 【Bertil】
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0]
输出:3
示例 2:
输入:nums = [3,4,-1,1]
输出:2
示例 3:
输入:nums = [7,8,9,11,12]
输出:1
提示:
- 1 <= nums.length <= 5 * 10^5
- -2^31 <= nums[i] <= 2^31 - 1
解题思路
1.首先将nums[i]放到对应的位置,如nums[0] = 1,nums[1] = 2,…,nums[6] = 7
2.然后遍历交换位置之后的数组,判断是否是对应位置,若不是,则直接返回当前索引值 + 1;若全都是,则直接返回nums.length + 1即可
代码
/** * @param {number[]} nums * @return {number} */
var firstMissingPositive = function(nums) {
for(let i = 0; i < nums.length; i++) {
// 循环nums,当前元素在(0,nums.length]之间,并且nums[nums[i]-1] != nums[i],则交换位置
while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]) {
const temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
}
}
for(let i = 0; i < nums.length; i++) {
// 循环交换位置之后的数组,判断第一个缺失的正数
if(nums[i] != i+1) {
return i+1;
}
}
// [1,2,3]
return nums.length + 1;
};
边栏推荐
- Double pointeur en langage C - - modèle classique
- Rviz仿真时遇到机器人瞬间回到世界坐标原点的问题及可能原因
- Sublime text in CONDA environment plt Show cannot pop up the problem of displaying pictures
- On the inverse order problem of 01 knapsack problem in one-dimensional state
- Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
- China polyether amine Market Forecast and investment strategy report (2022 Edition)
- R language ggplot2 visualization: place the title of the visualization image in the upper left corner of the image (customize Title position in top left of ggplot2 graph)
- @JsonBackReference和@JsonManagedReference(解决对象中存在双向引用导致的无限递归)
- Image, CV2 read the conversion and size resize change of numpy array of pictures
- hutool优雅解析URL链接并获取参数
猜你喜欢
JS inheritance method
[cloud native topic -45]:kubesphere cloud Governance - Introduction and overall architecture of enterprise container platform based on kubernetes
深度剖析C语言数据在内存中的存储
704 二分查找
Fairguard game reinforcement: under the upsurge of game going to sea, game security is facing new challenges
TCP/IP协议
【ROS】usb_cam相机标定
个人电脑好用必备软件(使用过)
C语言双指针——经典题型
Excellent software testers have these abilities
随机推荐
sys. argv
有效提高软件产品质量,就找第三方软件测评机构
电脑清理,删除的系统文件
ESP8266-RTOS物联网开发
Simple use of promise in uniapp
Deep analysis of C language pointer
Swagger setting field required is mandatory
Verrouillage [MySQL]
Indentation of tabs and spaces when writing programs for sublime text
ROS编译 调用第三方动态库(xxx.so)
Rviz仿真时遇到机器人瞬间回到世界坐标原点的问题及可能原因
TP-LINK enterprise router PPTP configuration
What is CSRF (Cross Site Request Forgery)?
poi追加写EXCEL文件
目标检测——Pytorch 利用mobilenet系列(v1,v2,v3)搭建yolov4目标检测平台
【MySQL】鎖
The harm of game unpacking and the importance of resource encryption
优秀的软件测试人员,都具备这些能力
Esp8266-rtos IOT development
What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway