• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode41.缺失的第一个正数|FirstMissingPositive

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/9901428.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.


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

示例 1:

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

示例 2:

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

示例 3:

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

说明:

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


8ms

1 class Solution {
2     func firstMissingPositive(_ nums: [Int]) -> Int {
3         if nums.count == 0 {return 1}
4         var nums = nums
5         for i in 0..<nums.count {while nums[i] >= 1 && nums[i] <= nums.count && nums[nums[i] - 1] != nums[i] {nums.swapAt(i, nums[i] - 1)}}
6         for i in 0..<nums.count {if nums[i] != i + 1 {return i + 1}}
7         return nums.count + 1
8     }
9 }

12ms

 1 class Solution {
 2     func firstMissingPositive(_ nums: [Int]) -> Int {
 3         guard nums.count > 0 else {
 4             return 1
 5         }
 6         var numsCopy = nums
 7         for  i in 0..<nums.count {
 8             while numsCopy[i] > 0 && numsCopy[i] < nums.count && numsCopy[numsCopy[i]-1] != numsCopy[i] {
 9                  numsCopy.swapAt(i, numsCopy[i]-1)
10             }
11         }
12         
13         for i in 0..<nums.count {
14             if numsCopy[i] != i + 1 {
15                 return i + 1
16             }
17         }
18         return nums.count + 1
19     }
20 }

12ms

 1 class Solution {
 2     func firstMissingPositive(_ nums: [Int]) -> Int {
 3     var newNums = nums
 4     for i in 0..<nums.count {
 5         while newNums[i] > i + 1 && newNums[i] <= nums.count && newNums[i] != newNums[newNums[i]-1] {
 6             if newNums[i] <= nums.count && newNums[i] != newNums[newNums[i]-1] {
 7                 let temp = newNums[i]
 8                 newNums[i] = newNums[temp-1]
 9                 newNums[temp-1] = temp
10             }
11         }
12         if newNums[i] > 0 && i + 1 > newNums[i] {
13             let temp = newNums[i]
14             newNums[i] = newNums[temp-1]
15             newNums[temp-1] = temp
16         }
17     }
18     var i = 0
19     while i < nums.count {
20         if i + 1 != newNums[i] {
21             return i + 1
22         }
23         i = i + 1
24     }
25     return i + 1
26     }
27 }

 16ms

 1 class Solution {
 2     func firstMissingPositive(_ nums: [Int]) -> Int {
 3         var set = Set<Int>()
 4         
 5         nums.forEach { set.insert($0) }
 6         
 7         for i in 0..<nums.count {
 8             if !set.contains(i + 1) {
 9                 return i + 1
10             }
11         }
12         
13         return nums.count + 1
14     }
15 }

16ms

 1 class Solution {
 2     func firstMissingPositive(_ nums: [Int]) -> Int {
 3         if(nums.count == 0){ return 1 }
 4         let maximum = nums.max()!
 5         if(maximum > 0){
 6             for i in 1...maximum{
 7                 if(!nums.contains(i)){
 8                     return i
 9                 }
10             }
11         }
12         return maximum + 1
13     }
14 }

20ms

 1 class Solution {
 2     func firstMissingPositive(_ nums: [Int]) -> Int {
 3         var nums = nums
 4         nums.append(-1)
 5         
 6         if nums.count == 0 {return 1}
 7         if nums.count == 1 {  return nums[0] == 1 ? 2 : 1 }
 8         
 9         for i in 0..<nums.count {
10             var val = nums[i]
11             while val < nums.count && val >= 0 && nums[val] != val {
12                 swap(&nums, i, val)
13                 val = nums[i]
14             }
15             if val != i  {
16                 nums[i] = -1
17             }
18         }
19         for i in 1..<nums.count {
20             if nums[i] == -1 {
21                 return i
22             }
23         }
24         return nums.count
25     }
26     
27     func swap(_ nums: inout [Int], _ i: Int, _ j: Int) {
28         let temp = nums[i]
29         nums[i] = nums[j]
30         nums[j] = temp
31     }
32 }

32ms

1 class Solution {
2     func firstMissingPositive(_ nums: [Int]) -> Int {
3         for i in 1 ..< Int.max {
4             if !nums.contains(i) { return i }
5         }
6         
7         return Int.max
8     }
9 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift学习笔记发布时间:2022-07-14
下一篇:
窥探Swift编程之错误处理与异常抛出发布时间:2022-07-14
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap