DAY 6
2
Software Development

[Day 6] 從LeetCode學演算法 - 0026. Remove Duplicates from Sorted Array (Easy)

``````Question:
Given a sorted nums array, remove the duplicates in-place such that each element appears only once 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.
``````
``````Example 1:
Given nums = [1,1,2],
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:
Given nums = [0,0,1,1,1,2,2,3,3,4],
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.
``````

Java:

``````class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length <= 1) return nums.length;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
``````

Python:

``````class Solution:
def removeDuplicates(self, nums):
if not nums: return 0
i, j = 0, 1
while j < len(nums):
if nums[i] != nums[j]:
i += 1
nums[i] = nums[j]
j += 1
return i + 1
``````

「時間複雜度跟空間複雜度為？」(O(N), O(1))

「如果不要求in-place，改成新開list/arraylist來做會比較快嗎？」
(不會，因為時間複雜度相同，但要額外花時間做記憶體配置)

「如果題目今天給的是未排序陣列要去除duplicate，

(使用HashMap/dict，將整個陣列掃過一遍，最後遍歷輸出)
(時間/空間複雜度為O(N), O(N))

0035. Search Insert Position (Easy)