当前位置:网站首页>LeetCode:41. Missing first positive number
LeetCode:41. Missing first positive number
2022-07-06 08:50:00 【Bertil】
Here's an unsorted array of integers nums , Please find the smallest positive integer that doesn't appear in it .
Please implement a time complexity of O(n) And solutions that use only constant level extra space .
Example 1:
Input :nums = [1,2,0]
Output :3
Example 2:
Input :nums = [3,4,-1,1]
Output :2
Example 3:
Input :nums = [7,8,9,11,12]
Output :1
Tips :
- 1 <= nums.length <= 5 * 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Their thinking
1. First of all, will nums[i] Put it in the right place , Such as nums[0] = 1,nums[1] = 2,…,nums[6] = 7
2. Then traverse the array after the exchange position , Determine whether it is the corresponding position , If it is not , Then directly return the current index value + 1; If it's all , Then return directly nums.length + 1 that will do
Code
/** * @param {number[]} nums * @return {number} */
var firstMissingPositive = function(nums) {
for(let i = 0; i < nums.length; i++) {
// loop nums, Current element in (0,nums.length] Between , also nums[nums[i]-1] != nums[i], Then switch places
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++) {
// Loop the array after swapping positions , Judge the first missing positive number
if(nums[i] != i+1) {
return i+1;
}
}
// [1,2,3]
return nums.length + 1;
};
边栏推荐
- Nacos 的安装与服务的注册
- LeetCode:498. 对角线遍历
- Export IEEE document format using latex
- UML图记忆技巧
- Charging interface docking tutorial of enterprise and micro service provider platform
- 查看局域网中电脑设备
- 深度剖析C语言指针
- 广州推进儿童友好城市建设,将探索学校周边200米设安全区域
- egg. JS project deployment online server
- R language ggplot2 visualization, custom ggplot2 visualization image legend background color of legend
猜你喜欢
深度剖析C语言数据在内存中的存储
软件卸载时遇到trying to use is on a network resource that is unavailable
可变长参数
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Indentation of tabs and spaces when writing programs for sublime text
LeetCode:498. 对角线遍历
Mobile phones and computers on the same LAN access each other, IIS settings
MYSQL卸载方法与安装方法
Sublime text using ctrl+b to run another program without closing other runs
查看局域网中电脑设备
随机推荐
pytorch训练好的模型在加载和保存过程中的问题
【嵌入式】使用JLINK RTT打印log
Detailed explanation of dynamic planning
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
LeetCode:劍指 Offer 42. 連續子數組的最大和
swagger设置字段required必填
【ROS】usb_ Cam camera calibration
Deep analysis of C language pointer
Export IEEE document format using latex
JS pure function
UML图记忆技巧
角色动画(Character Animation)的现状与趋势
目标检测——Pytorch 利用mobilenet系列(v1,v2,v3)搭建yolov4目标检测平台
Guangzhou will promote the construction of a child friendly city, and will explore the establishment of a safe area 200 meters around the school
Simple use of promise in uniapp
Image,cv2读取图片的numpy数组的转换和尺寸resize变化
JVM quick start
Generator parameters incoming parameters
Problems in loading and saving pytorch trained models
如何有效地进行自动化测试?