[JavaScript] LeetCode 41. First Missing Positive

題目概要

給定一個未排序的整數陣列nums,返回缺失的最小正整數。

時間複雜度必須是 O(n)

Example 1:

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

Example 2:

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

Example 3:

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

解題技巧

  • 因為負數在這題中沒有任何意義所以要篩掉,接著將陣列由小到大排序。
  • 如果 nums 長度為 0 或者 nums[0] 不為 1 時就返回1
  • 如果 nums 長度大於 0 且 nums[0] === 1,就代表缺失的正整數會在中間或者最後,我們可以用一個 for 迴圈遍歷 0 ~ nums.length,相鄰兩數兩兩比較,如果差值大於 1 就代表中間有兩數之間有缺失的數,返回該數即可。

程式碼

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    nums = nums.filter(item => item > 0); // 去掉負數

    if (nums.length) {
        nums.sort((a, b) => a - b); // 排序

        if (nums[0] !== 1) {
            // 如果沒有 1 就回傳 1
            return 1;
        } else {
            // 兩兩比較相差是否為 1, 如果不是就返回 nums[i] + 1
            for(let i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] - nums[i] > 1) {
                    return nums[i] + 1;
                }
            }
            // 否則回傳最後一個數 + 1
            return nums.pop() + 1;
        }
    } else return 1;
};
Rl2vrQU [JavaScript] LeetCode 41. First Missing Positive
0 0 評分數
Article Rating
訂閱
通知
guest
0 Comments
在線反饋
查看所有評論