C++實現(xiàn)LeetCode(41.首個缺失的正數(shù))
[LeetCode] 41. First Missing Positive 首個缺失的正數(shù)
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.
這道題讓我們找缺失的首個正數(shù)，由于限定了 O(n) 的時間，所以一般的排序方法都不能用，最開始博主沒有看到還限制了空間復雜度，所以想到了用 HashSet 來解，這個思路很簡單，把所有的數(shù)都存入 HashSet 中，然后循環(huán)從1開始遞增找數(shù)字，哪個數(shù)字找不到就返回哪個數(shù)字，如果一直找到了最大的數(shù)字（這里是 nums 數(shù)組的長度），則加1后返回結(jié)果 res，參見代碼如下：
解法一：
// NOT constant space
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
unordered_set<int> st(nums.begin(), nums.end());
int res = 1, n = nums.size();
while (res <= n) {
if (!st.count(res)) return res;
++res;
}
return res;
}
};
但是上面的解法不是 O(1) 的空間復雜度，所以需要另想一種解法，既然不能建立新的數(shù)組，那么只能覆蓋原有數(shù)組，思路是把1放在數(shù)組第一個位置 nums[0]，2放在第二個位置 nums[1]，即需要把 nums[i] 放在 nums[nums[i] - 1]上，遍歷整個數(shù)組，如果 nums[i] != i + 1, 而 nums[i] 為整數(shù)且不大于n，另外 nums[i] 不等于 nums[nums[i] - 1] 的話，將兩者位置調(diào)換，如果不滿足上述條件直接跳過，最后再遍歷一遍數(shù)組，如果對應(yīng)位置上的數(shù)不正確則返回正確的數(shù)，參見代碼如下：
解法二：
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) return i + 1;
}
return n + 1;
}
};
到此這篇關(guān)于C++實現(xiàn)LeetCode(41.首個缺失的正數(shù))的文章就介紹到這了,更多相關(guān)C++實現(xiàn)首個缺失的正數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++類成員函數(shù)后面加const問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
C語言數(shù)據(jù)結(jié)構(gòu)之棧和隊列的實現(xiàn)及應(yīng)用
棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實現(xiàn)方式。本文將以順序結(jié)構(gòu)實現(xiàn)棧，鏈表方式實現(xiàn)隊列，感興趣的小伙伴快跟隨小編一起學習一下吧2022-08-08
C++?使用getline()從文件中讀取一行字符串方法示例
這篇文章主要介紹了C++?使用getline()從文件中讀取一行字符串方法示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-09-09
這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)簡單學生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
PCM(Pulse Code Modulation)也被稱為脈沖編碼調(diào)制，是數(shù)字通信的編碼方式之一。這篇文章主要和大家聊聊C++中音頻PCM數(shù)據(jù)的相關(guān)操作，需要的可以參考一下2023-02-02
C++結(jié)合QT實現(xiàn)帶有優(yōu)先級的計算器功能
這篇文章主要介紹了C++結(jié)合QT實現(xiàn)帶有優(yōu)先級的計算器,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
C語言實現(xiàn)學生信息管理系統(tǒng)(文件版)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
下面小編就為大家?guī)硪黄獪\談C語言函數(shù)調(diào)用參數(shù)壓棧的相關(guān)問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-09-09
這篇文章主要為大家詳細介紹了C++成員函數(shù)中const的使用，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要給大家介紹了關(guān)于如何利用C++解決輸出鏈表中倒數(shù)k個結(jié)點的問題,文中通過實例代碼介紹的非常詳細,對大家學習或者使用C++具有一定的參考學習價值,需要的朋友可以參考下2021-12-12