プログラミングにおいて、データ構造の効率的な操作は非常に重要です。
特に、配列は最も基本的なデータ構造の一つであり、その中でもIn-place操作のアプローチは、追加のメモリを最小限に抑えることで、リソースの効率的な利用が可能となります。
配列のIn-Placeアルゴリズムの概要
新しいデータ構造を作成することなく、与えられた配列内で要素の変更、追加、削除を行う手法です。
この操作は、追加のメモリスペースをほとんどまたは全く使用しないことが特徴です。
多くの場合、配列の長さは固定で、操作を通じて配列内のデータが書き換えられます。
配列のIn-Placeアルゴリズムの使用例
反転アルゴリズム
配列の要素を反転させる最も簡単な方法は、先頭と末尾の要素を交換し、その間を徐々に狭めていくことです。
def reverse_array(arr):
start, end = 0, len(arr) - 1
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
データのフィルタリング
特定の条件に基づいて配列から要素を削除する場合、新しい配列を作る代わりに、条件を満たす要素だけを前方に移動させる方法があります。
def filter_array(arr, condition):
j = 0
for num in arr:
if condition(num):
arr[j] = num
j += 1
return arr[:j]
ゼロ埋め
ゼロでない要素を前に移動させ、すべてのゼロを配列の末尾に移動させるアルゴリズムです。
def move_zeroes(arr):
j = 0
for num in arr:
if num != 0:
arr[j] = num
j += 1
for i in range(j, len(arr)):
arr[i] = 0