力扣41(java)-缺失的第一个正数
2022/4/8 12:19:12
本文主要是介绍力扣41(java)-缺失的第一个正数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:
给你一个未排序的整数数组 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 * 105
-231 <= nums[i] <= 231 - 1
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
一、整体思路就是把数字i放在i-1的位置上
1.循环数组,如果数组中的数字在[1-n]范围内并且nums[nums[i] - 1] != nums[i](两数字不相等才进行交换
2.再循环遍历交换后的数组,如果位置i上的数字不等于i+1,则该位置上的数字i+1则对缺失的第一个正数,否则就是循环了整个数组都是符合的,那缺失的数就是n+1([1,2,3,4])
注意:
nums[nums[i] - 1] != nums[i]例如索引0位置上的元素3,然后nums[3-1]位置上的元素与nums[0]位置上的元素相等就没有必要交换了,只有不相等才交换。
代码:
交换过程:
二、
1.遍历数组,将所有的负数变成一个大于数组长度是数
2.再次遍历数组,将所有小于等于N的数做标记
3.遍历新数组,找到第一个正数的索引i,然后返回第一个缺失的正数为i+1
过程:
小知识:
1.Math.abs() 返回参数的绝对值。参数可以是 int, float, long, double, short, byte类型。
2.Java中的swap()函数,交换两个变量,通常在交换两个变量(如a, b)的时候会采用一个临时变量temp,用于存储变量a的值,然后将变量b的值赋给变量a,最后将temp赋给变量b完成两个变量的交换。
public static void swap(int a, int b) { int temp = a; a = b; b = temp; }
这篇关于力扣41(java)-缺失的第一个正数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)