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. ``` /** * @param {number[]} nums * @return {number} */ var firstMissingPositive = function(arr) { // 過濾掉非正整數 arr = arr.filter(item => item > 0) // 正整數數組是不是為空 if (arr.length) { // 升序，目的：方便從左到右取最小值arr[0] arr.sort((a, b) => a - b) // 如果第一個元素不為1，返回1 if (arr[0] !== 1) { return 1 } else { // 從左邊開始遍歷，只要下一個元素和當前元素差值>1, //說明當前元素的下一個值（+1） for (let i = 0, len = arr.length - 1; i < len; i++) { if (arr[i + 1] - arr[i] > 1) { return arr[i] + 1 } } // 如果數組是連續的正整數【1,2,3,4,5,6】 return arr.pop() + 1 } } else { return 1 } }; ``` ``` /** * @param {number[]} nums * @return {number} */ var firstMissingPositive = function(arr) { // 過濾掉非正整數 arr = arr.filter(item => item > 0) // 實現選擇排序，先拿到最小值，如果第一個元素不是1直接返回1， //如果是1，就要比相鄰元素差值 for (let i = 0, len = arr.length, min; i < len; i++) { min = arr[i] for (let j = i + 1; j < len; j++) { if (arr[j] < min) { let c = min min = arr[j] arr[j] = c } } arr[i] = min if (i > 0) { if (arr[i] - arr[i - 1] > 1) { return arr[i - 1] + 1 } } else { if (min !== 1) { return 1 } } } return arr.length ? arr.pop() + 1 : 1 }; ```