問題
今日はRearrange an array such that arr[i] = iの問題にチャレンジする。この問題は、0からn–1の範囲の長さnの要素のリストがあり、List[i]=iとなるように配列を再配置する。すべての要素が配列に存在するとは限らないので、要素が存在しない場合、配列には-1を表示する。
0から9の範囲の長さ10の要素のリストがあれば、本来であればoriginのようなリストになるが、inputには、0,5,7,8の要素がないので、その場所については-1を表示する。
# Input : [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1] # Output: [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9] # Origin: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
実装
まずは簡単な実装の内容でチャレンジする。インデックスを2つ使用し、iで「リストの位置」を決めて、そこに「入るべきリストの要素」をインデックスjで見つけてくるという方法。見つかれなければ、-1を変わりに代入しておく。
from typing import List
def Rearrange(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
for j in range(len_numbers):
if numbers[j] == i:
numbers[j], numbers[i] = numbers[i], numbers[j]
for i in range(len_numbers):
if numbers[i] != i:
numbers[i] = -1
if __name__ == '__main__':
numbers = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
print(numbers)
Rearrange(numbers)
print(numbers)
[-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
実装2
集合を使う方法。まずはリストの要素を集合の中に保存しておいて、そこからiで「リストの位置」を管理しつつ、集合の中にインデックスと一致する値があるかを検索。集合のなかにあるのであれば、その値をリストの適切な位置に入れていく、という方法。
from typing import List
def Rearrange2(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
cache = set()
# for i in range(len(A)):
# s.add(A[i])
cache = {numbers[i] for i in range(len_numbers)}
for i in range(len_numbers):
if i in cache:
numbers[i] = i
else:
numbers[i] = -1
return numbers
if __name__ == '__main__':
numbers = [-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
print(numbers)
Rearrange2(numbers)
print(numbers)
[-1, -1, 6, 1, 9, 3, 2, -1, 4, -1]
[-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
