LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個正數（First Mis

levius 發布于2019-08-23 16:46 / 2146人閱讀

摘要：小鹿題目算法思路桶排序思想。再遍歷數組，從下標開始判斷該下標是否存放規定的數據，如果不是則該下標就是這組數據中缺失的最小正整數。桶排序還可以實現在一組數據中查找重復的數據。

Time：2019/4/6
Title: First Missing Positive
Difficulty: Difficulty
Author: 小鹿

題目：First Missing Positive

Given an unsorted integer array, find the smallest missing?positive integer.

Note:

Your algorithm should run in O(n) time and uses constant extra space.

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

Solve：

▉ 算法思路：

桶排序思想。

遍歷第一遍數據，將數據存放到與下標相同的位置，遍歷第二遍數據，判斷每個下標對應的數據是否為下標值。如果不是，該數值就是當前確實的最小正整數;當數組遍歷完還有沒找到，那么數組的長度 + 1 就是缺失的最小正整數值。

▉ 算法步驟：

1、把數組的每一個下標當做是一個桶，每個桶只能存放一個數據（每個下標對應一個數據），我們規定桶中的數據和下標的對應關系是 0 下標對應數據1,1下標對應數據2，2下標對應數據3......，題目要求我們在O(n)的時間復雜度內找出一組數據中缺失的最小正整數。

2、遍歷第一遍數組中的數據，按照步驟 1 的規定，先判斷兩個當前下標對應的數據是否為規定的數據，如果不是，我們將該數據存放到規定的下標對應的數組中。然后交換的數據繼續進行判斷，直到該數據放到規定下標的數組中為止（小于等于 0 和數據大于數組長度的除外）。

3、再遍歷數組，從下標 0 開始判斷該下標是否存放規定的數據，如果不是則該下標就是這組數據中缺失的最小正整數。

4、如果數組中的數據都匹配對應的下標，那么最小正整數就是數組長度加一。

▉ 代碼實現：

/**
* @param {number[]} nums
* @return {number}
* 邊界條件：
* 1) 判斷傳入的數組是否為空。 
* 2) 判斷數組中的數據只有 1 個。
* 3) 交換數據時，判斷相同數據的處理。
*/
var firstMissingPositive = function(nums) {
    //遍歷數組
    for(let i = 0;i < nums.length;i++){
        //如果當前的數據不對應正確的下標 + 1 && 數據大于 0 && 長度小于等于數組
        while(nums[i] != i+1 && nums[i] > 0 && nums[i] <= nums.length){
            //判斷該數據對應正確位置的數據是否相同
            if(nums[nums[i]-1] == nums[i]) {
                //如果相同，將該下標對應的元素置為 0
                nums[i] = 0;
                break;
            }
            //如果不重復，就交換數據
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    //遍歷所有數據,找出缺失的最小正整數
    let index = 0;
    for(; index < nums.length; index++){
        if(nums[index] !== index+1){
            break;
        }
    }
    return index+1;
};

//測試
let arr =[];
console.log(firstMissingPositive(arr))

▉ 總結：

1、桶排序的思想。

2、桶排序還可以實現在一組數據中查找重復的數據。

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...

歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學編程的故事。

GPU云服務器云服務器小白的第一本python 代表企業的第二級域名為 javascript算法題匯編語言程序設計第二版課后題答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103274.html

LeetCode41.缺失的第一個正數 JavaScript

摘要：給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。示例輸入輸出示例輸入輸出示例輸入輸出答案參考給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。示例 1: 輸入: [1,2,0]輸出: 3 示例 2: 輸入: [3,4,-1,1]輸出: 2 示例 3: 輸入: [7,8,9,11,12]輸出: 1 答案參考： /** * @param {number[]} num...

ymyang 2019-08-23 15:17 評論0 收藏0
LeetCode 之 JavaScript 解答第8題 —— 字符串轉換整數（String to

摘要：當我們尋找到的第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續數字組合起來，作為該整數的正負號假如第一個非空字符是數字，則直接將其與之后連續的數字字符組合起來，形成整數。數字前正負號要保留。 Time：2019/4/19Title: String To IntegerDifficulty: MediumAuthor: 小鹿題目：String To Integer（字...

zhisheng 2019-08-23 17:03 評論0 收藏0
41. 缺失的第一個正數

摘要：問題問題描述給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。原因就在于使用的內置的函數的復雜度超過的比如的復雜度就是。問題問題描述給定一個未排序的整數數組，找出其中沒有出現的最小的正整數。說明你的算法的時間復雜度應為O(n)，并且只能使用常數級別的空間。解答首先因為只能使用常數級別的空間，就不能再建新的O(n)級的list，set等。然后就想到將列表去重去除非...

enali 2019-07-30 18:37 評論0 收藏0
LeetCode 之 JavaScript 解答第142題 —— 環形鏈表 II（Linked Li

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環鏈表的位置。首先，先判斷該單鏈表是否存在循環鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿題目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 評論0 收藏0
LeetCode 之 JavaScript 解答第141題 —— 環形鏈表 I（Linked Lis

摘要：小鹿題目算法思路兩種解題思路哈希表法遍歷鏈表，沒遍歷一個節點就要在哈希表中判斷是否存在該結點，如果存在，則為環否則，將該結點插入到哈希表中繼續遍歷。 Time：2019/4/7Title: Linked List CycleDifficulty: Easy Author:小鹿題目：Linked List Cycle I Given a linked list, determine ...

wangjuntytl 2019-08-23 16:49 評論0 收藏0