[Swift]LeetCode41. 缺失的第一个正数 | First Missing Positive

66 阅读 0 评论 44 点赞

我是靠谱客的博主纯情板凳，最近开发中收集的这篇文章主要介绍[Swift]LeetCode41. 缺失的第一个正数 | First Missing Positive，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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 }