刷題日記(13)Remove Duplicates from Sorted Array

Rachel Yeh
3 min readJan 5, 2021

Given a sorted array nums, remove the duplicates in-placesuch that each element appears only once and returns 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.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Constraints:

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums is sorted in ascending order.

解題思路:

  1. “in-place” 所以用雙指針,而且條件說list已經排好了
  2. 一根指針讀,一根指針寫
  3. 當快指針的值不等於慢指針時,慢指針加一格寫入快指針的值,之後快指針繼續走
  4. 注意不要不小心用到三指針,for loop裡面的i就可以當一個指針了
  5. 最後回傳慢指針+1,因為要的是長度

(main function)

  1. 設定一個base case如果傳進來的list是null或length 0回傳0
  2. 設定一個指針變數first等於0
  3. 開始for loop迴圈(i=0; i小於list的length; i++)

3.1 如果first指針的位置的值不等於i指針位置的值時,first先走一格之後寫入,i位置的值(first是慢指針,i是快指針)

4.結束for loop,代表遍歷list結束,回傳慢指針first+1的數值,因為答案要的是長度

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response