題目概要
給定一個未排序的整數陣列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; };
![[JavaScript] LeetCode 41. First Missing Positive Rl2vrQU Rl2vrQU [JavaScript] LeetCode 41. First Missing Positive](https://i.imgur.com/Rl2vrQU.png)
Latest posts by pluto (see all)
- Express + MongoDB 實作使用者增刪改查 API 及登入 API - 2022 年 7 月 2 日
- 解決 React Highcharts 資料筆數過多造成圖表渲染卡頓的情形 - 2022 年 6 月 28 日
- React 那些好看、有趣、實用的函式庫、組件庫推薦(2) - 2022 年 6 月 26 日