首页 > 其他 > 详细

缺失的正数

时间:2020-03-17 16:34:57      阅读:36      评论:0      收藏:0      [点我收藏+]

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

示例 1:

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

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

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

你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

 1 public class T41 {
 2     public int firstMissingPositive(int[] nums) {
 3         int len = nums.length;
 4         for (int i = 0; i < nums.length; i++) {
 5             while (nums[i] >= 1 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
 6                 swap(nums, i, nums[i] - 1);
 7             }
 8         }
 9         for (int i = 0; i < nums.length; i++) {
10             if (nums[i] != i + 1) {
11                 return i + 1;
12             }
13         }
14         return len + 1;
15     }
16 
17     private void swap(int[] nums, int i, int j) {
18         int temp = nums[i];
19         nums[i] = nums[j];
20         nums[j] = temp;
21     }
22 }

 

缺失的正数

原文:https://www.cnblogs.com/zzytxl/p/12511523.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!