First Missing Positive (H)
題目
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.
題意
找出無序陣列中最小的未出現的正整數，
思路
如果沒有空間限制，直接用hash很容易解答，既然有了空間限制，不妨就將原陣列本身變為hash表：在i下標處存放值為i+1的數，這樣只要再遍歷一遍陣列，找到第一個不符合這個規則的下標即可，
代碼實作
Java
class Solution {
public int firstMissingPositive(int[] nums) {
for (int i = 0; i < nums.length; i++) {
/*
* 整個演算法中最關鍵的操作就是判斷何時需要將當前值交換到對應下標處
* 需要同時滿足以下四點：
* 1. 當前值為正整數，不然無需處理
* 2. hash后的下標需要在陣列長度范圍內，不然會越界
* 3. 當前下標不是當前值對應的hash，不然會死回圈
* 4. 當前值與其hash下標對應的值不相等，不然會死回圈
*/
while (nums[i] > 0 && nums[i] - 1 < nums.length
&& nums[i] - 1 != i && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 進行到這步說明原陣列中的數正好是從1到nums.length的集合
return nums.length + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var firstMissingPositive = function (nums) {
let i = 0
while (i < nums.length) {
let j = nums[i] - 1
if (nums[i] <= 0 || nums[i] === i + 1 || nums[i] > nums.length || nums[j] === nums[i]) {
i++
} else {
[nums[i], nums[j]] = [nums[j], nums[i]]
}
}
for (let k = 0; k < nums.length; k++) {
if (k + 1 !== nums[k]) {
return k + 1
}
}
return nums.length + 1
}
參考
clnchanpin - leetCode 41.First Missing Positive (第一個丟失的正數) 解題思路和方法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38879.html
標籤：其他