Leetcode

[LeetCode] 80. Remove Duplicates from Sorted Array II

second9040

＊javascript solution
[Medium] 80. Remove Duplicates from Sorted Array II

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.

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,1,2,2,3]
Output: 5, nums = [1,1,2,2,3]
Explanation: Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

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

Constraints:

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

 

題意大概是
1. 已排序的陣列
2. 重複元素最多出現兩次

 

我的想法是用一個 map 記錄每個元素出現的次數，然後出現少於 2 次就保留起來。

 

var removeDuplicates = function(nums) {
  let newLength = 0, map = {}
  for (let i = 0; i < nums.length; i++) {
    if (typeof map[nums[i]] !== 'number') {
      map[nums[i]] = 1
      nums[newLength++] = nums[i] 
    } else if (map[nums[i]] < 2) {
      map[nums[i]] += 1
      nums[newLength++] = nums[i] 
    }
  }
  return newLength
};

 

result:

Runtime: 100 ms, faster than 9.57% of JavaScript online submissions for Remove Duplicates from Sorted Array II.

然後過是過了，但好像跑得有點慢吧...? 再來看看有沒有更好的解法。

 

 

下面這個解法我 google 的，主要思路是比較當前值與下一個值，如果不同就保留，相同的話，判斷出現次數來決定是否保留位置。

這邊主要就是注意初始值，newLength 從 0 開始，迴圈從 1 開始。
還有是要 ++newLength，因為是要保留下一個 index 的位置，所以不是 newLength++。

 

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

 

這個好一點。

Runtime: 92 ms, faster than 49.28% of JavaScript online submissions for Remove Duplicates from Sorted Array II.

 
題外話，一開始忘了刪 console.log，結果直接跑出個 636ms XDDD

 

參考資料
[用 Python 解 LeetCode] (003) 80. Remove Duplicates from Sorted Array II