一天一大 leet(缺失的第一個正數)難度:困難DAY-27

題目(難度:困難):

給你一個未排序的整數數組，請你找出其中沒有出現的最小的正整數。

示例

示例1

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

複制

示例2

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

複制

示例3

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

複制

提示

你的算法的時間複雜度應為O(n)，并且隻能使用常數級别的額外空間

抛磚引玉

從1開始遞增一個數字，遇到在數組中不存在則傳回
每個數字去數組中查詢一次，顯其複雜度似乎不滿足題目要求
除了includes，還可以是使用set、map輔助判斷是否存在

/**
 * @param {number[]} nums
 * @return {number}
 */
 // includes
var firstMissingPositive = function(nums) {
  let _result = 1;
  while (nums.includes(_result)) {
    _result++
  }
  return _result;
};
 // map
var firstMissingPositive = function(nums) {
  let _result = 1,map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i],nums[i]);
  }
  while(map.has(_result)){
    _result++;
  }
  return _result;
};

複制

官方答案

1. 哈希表

傳回最小正整數(n = nums.length):
- 結果的範圍：1到n+1
- 優先先剔除不符合邏輯的數-負數,用n+1
出現過在1到n+1的數字滿足範圍限制但是不符合要求，轉換成負值，标記其不符合要求
整理邏輯&代碼實作：

結果周遊的範圍是0到n，輸出1到n+1
循環轉換負數到n+1
周遊滿足小于n的數标記負号，使其排除
從0疊代整數判斷其小于n大于0，滿足則輸出其下一位數

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
  var n = nums.length;
  for (var i = 0; i < n; ++i) {
    if (nums[i] <= 0) {
      nums[i] = n + 1;
    }
  }
  for (var i = 0; i < n; ++i) {
    var num = Math.abs(nums[i]);
    if (num <= n) {
      nums[num - 1] = -Math.abs(nums[num - 1]);
    }
  }
  for (var i = 0; i < n; ++i) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  return n + 1;
};

複制

2. 置換

結果大于0小于n+1 如果數組中包含x∈[1,N]，

那麼恢複後，數組的是以為x−1 的元素為 x 按照這個邏輯重置下數組重置後，

傳回不滿足重置條件的數字

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
  var n = nums.length;
    for (var i = 0; i < n; ++i) {
        while (nums[i] > 0 && 
               nums[i] <= n && 
               nums[nums[i] - 1] != nums[i]
        ) {
            var temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for (var i = 0; i < n; ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
};

複制