Remove Duplicates
ソートされた数値の配列が引数として渡されて、そこからすべての重複を削除します。新たなデータ構造は使用せず
In-place で重複を削除した後、配列の新しい長さを返します。
例
Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4 ([2, 3, 6, 9])
Input: [2, 2, 2, 11]
Output: 2 ([2, 11])
Solution
# The time complexity: O(N)
# Space Complexity: O(1)
def remove_duplicates(arr):
# index of the next non-duplicate element
next_non_duplicate = 1
i = 1
while(i < len(arr)):
if arr[next_non_duplicate - 1] != arr[i]:
arr[next_non_duplicate] = arr[i]
next_non_duplicate += 1
i += 1
return next_non_duplicate
類題
並べ替えられていない数値の配列とターゲットの「キー」を指定して、「キー」と一致する要素全て削除し、配列の新しい長さを返します。
例
Input: [3, 2, 3, 6, 3, 10, 9, 3], Key=3
Output: 4 ([2, 6, 10, 9])
Input: [2, 11, 2, 2, 1], Key=2
Output: 2 ([11, 1])
実装
# The time complexity: O(N)
# Space Complexity: O(1)
def remove_element(arr, key):
nextElement = 0 # index of the next element which is not 'key'
for i in range(len(arr)):
if arr[i] != key:
arr[nextElement] = arr[i]
nextElement += 1
return nextElement