成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個(gè)正數(shù)（First Mis

levius / 2187人閱讀

摘要：小鹿題目算法思路桶排序思想。再遍歷數(shù)組，從下標(biāo)開(kāi)始判斷該下標(biāo)是否存放規(guī)定的數(shù)據(jù)，如果不是則該下標(biāo)就是這組數(shù)據(jù)中缺失的最小正整數(shù)。桶排序還可以實(shí)現(xiàn)在一組數(shù)據(jù)中查找重復(fù)的數(shù)據(jù)。

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：
▉ 算法思路：
桶排序思想。
遍歷第一遍數(shù)據(jù)，將數(shù)據(jù)存放到與下標(biāo)相同的位置，遍歷第二遍數(shù)據(jù)，判斷每個(gè)下標(biāo)對(duì)應(yīng)的數(shù)據(jù)是否為下標(biāo)值。如果不是，該數(shù)值就是當(dāng)前確實(shí)的最小正整數(shù);當(dāng)數(shù)組遍歷完還有沒(méi)找到，那么數(shù)組的長(zhǎng)度 + 1 就是缺失的最小正整數(shù)值。
▉ 算法步驟：
1、把數(shù)組的每一個(gè)下標(biāo)當(dāng)做是一個(gè)桶，每個(gè)桶只能存放一個(gè)數(shù)據(jù)（每個(gè)下標(biāo)對(duì)應(yīng)一個(gè)數(shù)據(jù)），我們規(guī)定桶中的數(shù)據(jù)和下標(biāo)的對(duì)應(yīng)關(guān)系是 0 下標(biāo)對(duì)應(yīng)數(shù)據(jù)1,1下標(biāo)對(duì)應(yīng)數(shù)據(jù)2，2下標(biāo)對(duì)應(yīng)數(shù)據(jù)3......，題目要求我們?cè)贠(n)的時(shí)間復(fù)雜度內(nèi)找出一組數(shù)據(jù)中缺失的最小正整數(shù)。
2、遍歷第一遍數(shù)組中的數(shù)據(jù)，按照步驟 1 的規(guī)定，先判斷兩個(gè)當(dāng)前下標(biāo)對(duì)應(yīng)的數(shù)據(jù)是否為規(guī)定的數(shù)據(jù)，如果不是，我們將該數(shù)據(jù)存放到規(guī)定的下標(biāo)對(duì)應(yīng)的數(shù)組中。然后交換的數(shù)據(jù)繼續(xù)進(jìn)行判斷，直到該數(shù)據(jù)放到規(guī)定下標(biāo)的數(shù)組中為止（小于等于 0 和 數(shù)據(jù)大于數(shù)組長(zhǎng)度的除外）。


3、再遍歷數(shù)組，從下標(biāo) 0 開(kāi)始判斷該下標(biāo)是否存放規(guī)定的數(shù)據(jù)，如果不是則該下標(biāo)就是這組數(shù)據(jù)中缺失的最小正整數(shù)。


4、如果數(shù)組中的數(shù)據(jù)都匹配對(duì)應(yīng)的下標(biāo)，那么最小正整數(shù)就是數(shù)組長(zhǎng)度加一。
▉ 代碼實(shí)現(xiàn)：
/**
* @param {number[]} nums
* @return {number}
* 邊界條件：
* 1) 判斷傳入的數(shù)組是否為空。 
* 2) 判斷數(shù)組中的數(shù)據(jù)只有 1 個(gè)。
* 3) 交換數(shù)據(jù)時(shí)，判斷相同數(shù)據(jù)的處理。
*/
var firstMissingPositive = function(nums) {
    //遍歷數(shù)組
    for(let i = 0;i < nums.length;i++){
        //如果當(dāng)前的數(shù)據(jù)不對(duì)應(yīng)正確的下標(biāo) + 1 && 數(shù)據(jù)大于 0 && 長(zhǎng)度小于等于數(shù)組
        while(nums[i] != i+1 && nums[i] > 0 && nums[i] <= nums.length){
            //判斷該數(shù)據(jù)對(duì)應(yīng)正確位置的數(shù)據(jù)是否相同
            if(nums[nums[i]-1] == nums[i]) {
                //如果相同，將該下標(biāo)對(duì)應(yīng)的元素置為 0
                nums[i] = 0;
                break;
            }
            //如果不重復(fù)，就交換數(shù)據(jù)
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    //遍歷所有數(shù)據(jù),找出缺失的最小正整數(shù)
    let index = 0;
    for(; index < nums.length; index++){
        if(nums[index] !== index+1){
            break;
        }
    }
    return index+1;
};

//測(cè)試
let arr =[];
console.log(firstMissingPositive(arr))
▉ 總結(jié)：
1、桶排序的思想。
2、桶排序還可以實(shí)現(xiàn)在一組數(shù)據(jù)中查找重復(fù)的數(shù)據(jù)。

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


歡迎關(guān)注我個(gè)人公眾號(hào)：「一個(gè)不甘平凡的碼農(nóng)」，記錄了自己一路自學(xué)編程的故事。

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/103274.html

相關(guān)文章

  • LeetCode41.缺失的第一個(gè)正數(shù) JavaScript

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

    ymyang 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第8題 —— 字符串轉(zhuǎn)換整數(shù) （String to

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

    zhisheng 評(píng)論0 收藏0

  • 41. 缺失的第一個(gè)正數(shù)

    摘要：?jiǎn)栴}問(wèn)題描述給定一個(gè)未排序的整數(shù)數(shù)組，找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。原因就在于使用的內(nèi)置的函數(shù)的復(fù)雜度超過(guò)的比如的復(fù)雜度就是。 問(wèn)題 問(wèn)題描述 給定一個(gè)未排序的整數(shù)數(shù)組，找出其中沒(méi)有出現(xiàn)的最小的正整數(shù)。 說(shuō)明 你的算法的時(shí)間復(fù)雜度應(yīng)為O(n)，并且只能使用常數(shù)級(jí)別的空間。 解答 首先因?yàn)橹荒苁褂贸?shù)級(jí)別的空間，就不能再建新的O(n)級(jí)的list，set等。然后就想到將列表去重去除非...

    enali 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第142題 —— 環(huán)形鏈表 II（Linked Li

    摘要：說(shuō)明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個(gè)快慢指針?lè)謩e指向鏈表的頭部，每次移動(dòng)兩步，每次移動(dòng)一步，移動(dòng)的步數(shù)是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿 題目：Linked List Cycle II Giv...

    whidy 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第141題 —— 環(huán)形鏈表 I（Linked Lis

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

    wangjuntytl 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<