80. Remove Duplicates from Sorted Array II

tags: online_judge, c

給定一個已排序的 int 陣列, 要求移除陣列內出現數超過兩次的元素, 同時要求 O(1) 空間複雜度。

難度不高的 Medium 題目, 但需要注意邊界問題。
由於給定的陣列有經過排序, 因此只需要和上一個元素作比對, 而不必對整個陣列作搜尋。
發現同樣的元素時, 則把 flag 改為 true, 若 flag 已經為 true, 則代表元素已經出現超過兩次。可以跳過該元素。

注意給定陣列大小可為 0, 需要進行例外處理。

---

題目

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

---

解答

int removeDuplicates(int* nums, int numsSize){
    
    if(numsSize<1){
        return numsSize;
    }
    
    int count = 1;
    int hit = 0;        
    int i;
    for(i = 1; i < numsSize; i++){
        
        if(nums[count-1] == nums[i]){
            if(hit == 1){
                continue;
            }
            hit = 1;
        }
        else{
            hit = 0;
        }
        
        nums[count] = nums[i];
        count++;
        
    }
    
    return count;
    
}

---

成績

---