Leetcode

[LeetCode] 26. Remove Duplicates from Sorted Array

second9040

＊javascript solution
[easy] 26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such 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.

 

做完 NO.27 馬上做 NO.26，發現並不是很了解題目中那個 in-place 是什麼意思，google 了還是看不懂，不過好像沒看懂也不影響解題(?

 
總之就是
1. 不能開新陣列
2. 時間複雜度要是 O(1)，這個昨天我剛看過還記得，簡單說就是最好跟最壞的情形所用的時間要一樣。
3. 刪除陣列中重複的元素後 return

 

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

 

第一次眼殘沒看到可能會有負整數，改個條件就好了。