創作內容

0 GP

【Leetcode】41. First Missing Positive 解題&分析〈C++〉

作者:渾沌沌│2019-08-12 15:51:39│贊助:0│人氣:129
心得

其實這題不難,但為何這題花了我不少時間來想呢,還不是為了拚時間複雜度O(n)內呢!
雖然最後還是參考了別人的解法,不過也是讓我大開眼界啦。



題目

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



說明

這個解法與 Cycle Sort 有些相似。我們將其搬移至其所
能代表該值的索引值,便可達到分類的目的。
舉例來說,[3,1,2] 我們可以試著把 3 移動到 index = 2 的地方,
然而,那個位置原本就有一個 2,因此我們把 2 搬移到 index = 1 的地方,
依此類推,最後陣列會變成 [1,2,3]。

可能會有人問說,那重複值、負值或超過陣列大小的值該如何處理?
例如 [3,-1,7,2] 該怎麼辦呢?
答案是,
忽略吧!
我們先做相同的操作,陣列會變成 [7,-1,2,3]。
那麼變成這樣有什麼好處呢?我們可以試著分析一下:
假設今天有N個數,即陣列大小為N。
那可能會有以下情況:
1. 剛好滿足1~N
Ex: [3,1,2,4] => [1,2,3,4]
這是最顯而易見的情況, 我們只要求N+1,也就是5即可。
2. 有重複數字
Ex: [4,3,1,3] => [1,3,3,4]
仔細看看,我們需要的值也是由1開始往後檢查,
發現第一個3不在他所在的位置,所以顯然2是我們要找的。
3. 超出範圍
Ex: [8,-1,2,3] => [8,2,3,-1]
一旦我們無視超出範圍的值,同樣也只要找到不符合的部分即可。

綜上所述,我們便利用這些共同點,只要依次找到不符合的就是答案囉!



效能

Best Runtime : 0ms - Faster than 100.00%
Best Memory Usage : 8.6MB - Less than 86.00%

Submitted on : 2019/08/12



程式碼


引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4492749
All rights reserved. 版權所有,保留一切權利

相關創作

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★jasonacbb 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:【Coding】 JAV...

追蹤私訊切換新版閱覽

作品資料夾

enchnater000all
SRPG 眼中的世界 搶先體驗中! https://store.steampowered.com/app/811070看更多我要大聲說昨天11:17


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】