LeetCode Js-26. Remove Duplicates from Sorted Array

    AllenLi
    LeetCode Js-Array

    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.
    Return k after placing the final result in the first k slots of nums.
    Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

    給予一個nums(整數陣列)按照非遞減排序(小到大)，移除nums中重複的數值且每個數值僅出現一次，然而nums的數值排序不變。
將結果放入nums的前方，並回傳nums的數量
不使用額外的陣列空間，且必須在原陣列中計算。

    Example 1:

    Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

    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 k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

    Solution:
    1. 如果nums為無效或空值，則為傳0。
    2. 宣告count為確認次數=字串長度。
    3. 「For迴圈」進行陣列中數值倆倆比對。

    count = 0, i = 1
[      0,      1,      2]
  nums[0] nums[1] 
  nums[0]         nums[2]

    4. 「if條件」
    不相同時count+=1，且變更原陣列的數值。
    相同時count不變，且依序往後比較數值。
    5. 完成「for回圈」，return count+1的數值。

    box   = [1, 2, 3]
Array =  0  1  2
box.length = Array + 1

    Code 1: BigO(n)

    var removeDuplicates = function (nums: number[]): number {
    if (nums === null || nums.length === 0) return 0
    let count = 0
    for (let i = 1; i < nums.length; i++) {
        if (nums[count] !== nums[i]) {
            count++
            nums[count] = nums[i]
            }
    }
    return count + 1
};

    FlowChart:
    Example 1

    step.1
nums = [      1,      1,      2]
         nums[0] nums[1] 
count = 0

step.2
nums = [      1,      1,      2]
         nums[0]         nums[2] 
count => 0 + 1 = 1
nums[1] = nums[2]
=>nums [      1,      2,      2]

step.3
return count++ => 1 + 1 = 2

    Example 2

    step.1
nums = [      0,      0,      1,      1,      1,      2,      2,      3,      3,      4]
         nums[0] nums[1] 
count = 0

step.2
nums = [      0,      0,      1,      1,      1,      2,      2,      3,      3,      4]
         nums[0]         nums[2] 
count => 0 + 1 = 1
nums[1] = nums[2]
=> nums = [      0,      1,      1,      1,      1,      2,      2,      3,      3,      4]

step.3
nums = [      0,      1,      1,      1,      1,      2,      2,      3,      3,      4]
                 nums[1]         nums[3] 
count = 1

step.4
nums = [      0,      1,      1,      1,      1,      2,      2,      3,      3,      4]
                 nums[1]                 nums[4] 
count = 1

step.5
nums = [      0,      1,      1,      1,      1,      2,      2,      3,      3,      4]
                 nums[1]                         nums[5] 
count => 1 + 1 = 2
nums[1] = nums[5]
=> nums = [      0,      1,      2,      1,      1,      2,      2,      3,      3,      4]

step.6
nums = [      0,      1,      2,      1,      1,      2,      2,      3,      3,      4]
                         nums[2]                         nums[6] 
count = 2

step.7
nums = [      0,      1,      2,      1,      1,      2,      2,      3,      3,      4]
                         nums[2]                                 nums[7] 
count => 2 + 1 = 3
nums[3] = nums[7]
=> nums = [      0,      1,      2,      3,      1,      2,      2,      3,      3,      4]

step.8
nums = [      0,      1,      2,      3,      1,      2,      2,      3,      3,      4]
                                 nums[3]                                 nums[8] 
count = 3

step.9
nums = [      0,      1,      2,      3,      1,      2,      2,      3,      3,      4]
                                 nums[3]                                         nums[9] 
count => 3 + 1 = 4
nums[4] = nums[9]
=> nums = [      0,      1,      2,      3,      4,      2,      2,      3,      3,      4]

return count++ => 4 + 1 = 5

    Code 2: BigO(n)

    var removeDuplicates = function (nums: number[]): number {
  const uniq = new Set(nums);
  const num = Array.from(uniq)

  for (let i = 0; i < nums.length; i++) {
    nums[i] = num[i];
  }
  return num.length
};

    Related Posts