iT邦幫忙

2024 iThome 鐵人賽

0
佛心分享-刷題不只是刷題

刷經典 LeetCode 題目系列 第 66

經典LeetCode 26. Remove Duplicates from Sorted Array

  • 分享至 

  • xImage
  •  

題目:
給一個排序過的陣列 nums,請你「原地」移除重複的元素,使每個元素只出現一次,並回傳移除後的新長度。不要使用額外的空間,必須在原地修改來源的陣列。

範例:

輸入:
nums = [0,0,1,1,1,2,2,3,3,4]

輸出:
長度 = 5, nums = [0,1,2,3,4]

函式應回傳新長度 5,並將前五個元素修改為 [0, 1, 2, 3, 4]。你不需要考慮陣列中超出新長度之後的元素。

解題思路

使用快慢指標,i 慢指標為確定的不重複結果,j 快指標則是找跟 i 不同的元素,找到後並覆蓋到i+1的位置,遍歷完以後 i+1 就是最後的新長度。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int j = 1; j < nums.size(); j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i+1;
    }
};

時間複雜度:O(n)
空間複雜度:O(1)

參考:
#26. Remove Duplicates from Sorted Array


上一篇
經典LeetCode 33. Search in Rotated Sorted Array
系列文
刷經典 LeetCode 題目66
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言