力扣00041.缺失的第一个正数

发表于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟
缺失的第一个正数、数组、哈希表、困难

题目描述

给你一个未排序的整数数组 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 * 10^5$
  • $-2^{31} <= nums[i] <= 2^{31} - 1$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            while (1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

结果

执行用时 : 39 ms, 击败 94.56% 使用 C++ 的用户

内存消耗 : 42.63 MB, 击败 25.68% 使用 C++ 的用户

Java

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

结果

执行用时 : 1 ms, 击败 98.51% 使用 Java 的用户

内存消耗 : 53.84 MB, 击败 68.75% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

结果

执行用时 : 69 ms, 击败 72.86% 使用 Python 的用户

内存消耗 : 19.07 MB, 击败 90.86% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1

结果

执行用时 : 74 ms, 击败 % 使用 Python3 的用户

内存消耗 : 27.45 MB, 击败 % 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int firstMissingPositive(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; ++i) {
        while (1 <= nums[i] && nums[i] <= numsSize && nums[nums[i] - 1] != nums[i]) {
            swap(&nums[nums[i] - 1], &nums[i]);
        }
    }
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return numsSize + 1;
}

结果

执行用时 : 39 ms, 击败 95.26% 使用 C 的用户

内存消耗 : 10.66 MB, 击败 92.39% 使用 C 的用户

C#

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

结果

执行用时 : 142 ms, 击败 66.90% 使用 C# 的用户

内存消耗 : 57.28 MB, 击败 27.47% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        while (1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    for (let i = 0; i < n; ++i) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    return n + 1;
};

结果

执行用时 : 74 ms, 击败 70.49% 使用 JavaScript 的用户

内存消耗 : 55.44 MB, 击败 36.87% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function firstMissingPositive(nums: number[]): number {
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        while (1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    for (let i = 0; i < n; ++i) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

结果

执行用时 : 74 ms, 击败 83.62% 使用 TypeScript 的用户

内存消耗 : 57.48 MB, 击败 29.94% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function firstMissingPositive($nums) {
        $n = count($nums);
        for ($i = 0; $i < $n; ++$i) {
            while (1 <= $nums[$i] && $nums[$i] <= $n && $nums[$nums[$i] - 1] != $nums[$i]) {
                [$nums[$nums[$i] - 1], $nums[$i]] = [$nums[$i], $nums[$nums[$i] - 1]];
            }
        }
        for ($i = 0; $i < $n; ++$i) {
            if ($nums[$i] !== $i + 1) {
                return $i + 1;
            }
        }
        return $n + 1;
    }
}

结果

执行用时 : 118 ms, 击败 76.19% 使用 PHP 的用户

内存消耗 : 26.82 MB, 击败 100.00% 使用 PHP 的用户

Swift

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

结果

执行用时 : 151 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 19.63 MB, 击败 14.14% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    fun firstMissingPositive(nums: IntArray): Int {
        val n = nums.size
        for (i in 0 until n) {
            while (1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                nums[nums[i] - 1] = nums[i].also { nums[i] = nums[nums[i] - 1] }
            }
        }
        for (i in 0 until n) {
            if (nums[i] != i + 1) {
                return i + 1
            }
        }
        return n + 1
    }
}

结果

执行用时 : 318 ms, 击败 93.88% 使用 Kotlin 的用户

内存消耗 : 49.80 MB, 击败 89.80% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  int firstMissingPositive(List<int> nums) {
    final n = nums.length;
    for (var i = 0; i < n; ++i) {
      while (1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
        final temp = nums[i];
        nums[i] = nums[temp - 1];
        nums[temp - 1] = temp;
      }
    }
    for (var i = 0; i < n; ++i) {
      if (nums[i] != i + 1) {
        return i + 1;
      }
    }
    return n + 1;
  }
}

结果

执行用时 : 312 ms, 击败 100.00% 使用 Dart 的用户

内存消耗 : 160.04 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		for 1 <= nums[i] && nums[i] <= n && nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

结果

执行用时 : 38 ms, 击败 92.71% 使用 Go 的用户

内存消耗 : 7.73 MB, 击败 97.26% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# @param {Integer[]} nums
# @return {Integer}
def first_missing_positive(nums)
  n = nums.length
  (0...n).each do |i|
    while 1 <= nums[i] && nums[i] <= n && nums[nums[i] - 1] != nums[i]
      nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
    end
  end
  (0...n).each do |i|
    return i + 1 if nums[i] != i + 1
  end
  n + 1
end

结果

执行用时 : 122 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 210.50 MB, 击败 33.33% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
object Solution {
  def firstMissingPositive(nums: Array[Int]): Int = {
    val n = nums.length
    def swap(i: Int, j: Int): Unit = {
      val temp = nums(i)
      nums(i) = nums(j)
      nums(j) = temp
    }
    for (i <- 0 until n) {
      while (1 <= nums(i) && nums(i) <= n && nums(nums(i) - 1) != nums(i)) {
        swap(i, nums(i) - 1)
      }
    }
    for (i <- 0 until n) {
      if (nums(i) != i + 1) {
        return i + 1
      }
    }
    n + 1
  }
}

结果

执行用时 : 696 ms, 击败 92.31% 使用 Scala 的用户

内存消耗 : 77.17 MB, 击败 84.62% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn first_missing_positive(mut nums: Vec<i32>) -> i32 {
        let n = nums.len();
        for i in 0..n {
            while 1 <= nums[i] && nums[i] <= n as i32 && nums[(nums[i] - 1) as usize] != nums[i] {
                let index = (nums[i] - 1) as usize;
                nums.swap(i, index);
            }
        }
        for i in 0..n {
            if nums[i] != (i + 1) as i32 {
                return (i + 1) as i32;
            }
        }
        (n + 1) as i32
    }
}

结果

执行用时 : 4 ms, 击败 89.19% 使用 Rust 的用户

内存消耗 : 2.98 MB, 击败 49.38% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户