Help us understand the problem. What is going on with this article?

アルゴリズム 体操20 Remove Duplicates

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away