iT邦幫忙

2024 iThome 鐵人賽

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

刷題筆記系列 第 3

[Day3]Remove Duplicates from Sorted Array

  • 分享至 

  • xImage
  •  

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:
• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

給定一個非遞減排序的整數陣列" nums",要求原地(in-place)删除重複出現的元素,使每個唯一的元素在陣列中僅出現一次,且需保持元素的相對順序不變,最後回傳陣列" nums" 中唯一元素的個數 k。
為了滿足要求需達到以下條件:

• 修改陣列 nums,使得 nums 的前 k 個元素包含原始順序中的唯一元素。nums中的其他元素可以忽略,陣列的大小也可以改變。
• 回傳 k,就是 nums 中所有唯一元素的個數。

範例如下:
https://ithelp.ithome.com.tw/upload/images/20240815/20168667i8Ws1cx4nF.png


先拆解題目
1.先設定兩個指針 pointer1 與 pointer 2,且兩指針分別在index 0、index 1的位置
2.使用for loop,讓for loop中的pointer2迭代,並讓pointer2從nums[1]的位置開始迭代
( 這意味著 pointer2 會跑在 pointer1 的前面)
3-1.假設 pointer1 跟 pointer2 數值相同,則不須交換
https://ithelp.ithome.com.tw/upload/images/20240815/20168667m1GzYrFMb2.png
3-2.假設 pointer2 跟 pointer1 數值不相同,則pointer1與pointer2的整數交換。交換後,再往陣列nums的右側移動(這樣做的目的是可以把唯一元素都換到nums的左側)
https://ithelp.ithome.com.tw/upload/images/20240815/20168667LbqDAIebR7.png
4.最後,pointer1停留的位置會是整個陣列中 最後一個唯一元素,再+1把index轉換成k值

轉換成程式碼如下

var removeDuplicates = function(nums) {
    let pointer1 = 0;
    for (let pointer2 = pointer1 + 1; pointer2 < nums.length; i++){
        if (nums[pointer1] !== nums[pointer2]){
            pointer1++;
            nums[pointer1] = nums[pointer2];
        }
    }
    return pointer1++;
}

上一篇
[Day2] Pattern - Two Pointers
下一篇
[Day4] Intersection of Two Arrays II
系列文
刷題筆記20
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言