iT邦幫忙

1

【c/c++學習筆記】解題記錄Leetcode26. Remove Duplicates from Sorted Array

本文適合對象: 對c/c++有初步認識者、初學練習者
題目來源: Leetcode26. Remove Duplicates from Sorted Array

題目敘述: 給定一個排序過的陣列,例如nums = [0,0,1,1,1,2,2,3,3,4],去除重複的元素並回傳新的長度。
例如本範例的結果為: nums=[0,1,2,3,4],回傳新長度5

函數型式: int removeDuplicates(vector<int>& nums);
題目分析: 其實題目的邏輯不難,但可以練習c++ vector操作,稍有不慎很容易寫錯,唯有自己真正寫過並debug方能成長。因為陣列是排序過的,所以重複的元素一定會相鄰,只要檢查元素與上一個元素是相同的就刪除即可,小馬嘗試過程的程式如下

debug心路歷程分享

<錯誤程式碼一>

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    for(it=it+1;it!=nums.end();it++){
        if(*it==n){
            nums.erase(it); //錯誤:一旦迭代器刪除就失效了
        }
        else{
            n=*it;
        }
    }
    return nums.size();    
}

因為在做nums.erase(it);這行時,
可能會無效化迭代器導致程式的錯誤,
應改為it=nums.erase(it);

<錯誤程式碼二>

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    for(it=it+1;it!=nums.end();it++){
        if(*it==n){
            it=nums.erase(it); //錯誤:一旦迭代器刪除就失效了
        }
        else{
            n=*it;
        }
    }
    return nums.size();    
}

這樣寫仍然會有問題,
因為若刪除了一個迭代器,
it=nums.erase(it);便會指向下一個元素,
如果在for迴圈再做it++的話,
便會再跳過一個元素,
最後程式改寫如下

<正確程式碼>

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    for(it=it+1;it!=nums.end();){
        if(*it==n){
            it=nums.erase(it);
        }
        else{
            n=*it;
            it++; //若沒有刪除元素,才需要推進迭代器
        }
    }
    return nums.size();    
}

<錯誤程式碼三>

還有一個比較不容易發現問題的錯誤版本,
便是嘗試先儲存以end()回傳的迭代器。

int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0; //若vector本身為空,直接回傳0
    vector<int>::iterator it = nums.begin();
    int n=nums[0]; //記錄vector的第一個元素
    vector<int>::iterator end_it = nums.end();
    for(it=it+1;it!=end_it;){
        if(*it==n){
            it=nums.erase(it);
        }
        else{
            n=*it;
            it++; //若沒有刪除元素,才需要推進迭代器
        }
    }
    return nums.size();    
}

本程式跟正解程式僅僅差在將for(it=it+1;it!=nums.end();)拆成
vector<int>::iterator end_it = nums.end();
for(it=it+1;it!=end_it;) 兩行來寫,
乍看之下好像意思完全一樣,
但事實上如果我們對vector新增或刪除元素,
原先end()所回傳的元素便會無效化,
故需要每次做for迴圈迭代時都重新產生新的nums.end()做為條件判斷


尚未有邦友留言

立即登入留言