LeetCodeの「Build Array from Permutation」という問題を解きました1。これは配列numsが与えられたとき、ans[i]=nums[nums[i]]となる配列ansを返すという問題です。ただし、numsの中身はlen(nums)(=n)未満の一意な正の整数となっています。例えば
nums=[0,1,3,4,2] #→ansは[0,1,4,2,3]です。
難しいのはフォローアップで、これを定数メモリで解けという指示が与えられていました。配列問題を定数メモリで解くためには、入力配列自体をin-placeで出力配列に書き直すことが必要です。しかし、安直に値を書き換えるともともと入っていた値の情報が失われます。これを防ぐ方法として、値を読み出してから書き込むというものがあります。定数メモリで実行するためには、値は定数個しか読み出すことができません。ここで自分はギブアップしてしまいました。
SolutionはLeetCode上にはなく、ググってMediumで見つけました。かなり汎用性が高い手法なので、色々考察してみました。
Mediumで紹介されていたSolutionとは、値を安直に書き換える代わりに、もとの値の情報と、書き換え後の情報を保持した値を配列に格納し、最後に書き換え後の情報だけを各要素から抜き出すという手法です。具体的には、
for i in range(len(nums)):
nums[i]=n*(nums[nums[i]]%n)+nums[i] #注：右辺評価時にはnums[i]はまだ書き換え前なのでnums[i]%nとしなくてよい
for i in range(len(nums)):
nums[i]=int(nums[i])とするというものです。ループ内の操作でnums[i]には
- nで割った商が書き換え後の値
- nで割った余りが書き換え前の値
という値が入ります。
性質1 この手法が使える配列長の最大値がある
この手法はnums内の要素がint192なのに対し、値の取りうる範囲がnまでであり、冗長なビットがあることを利用して定数メモリを実現しています。書き換え後の値を保持するためには、冗長ビット数が足りている必要があります。
エンコード後の値の最大値は、(n-1)^2となります。これは、もとのデータがnums[n-1]=n-1であるときに出現します。従って、numsのデータ型はlog2[(n-1)^2+1]≒2log2(n-1)ビット以上必要です。このことから、この手法が成り立つには2log2(n-1)<=1922が成り立つ、つまりn<=2^96+1が成り立たなければなりません。データ型が収容できるビット数の半分までということですね。
性質2 別解
もとのデータがceil(log2(n))ビットで表せるので、書き込み後の値をint(ceil(log2(n)))ビット左にシフトしてもとの値とビットごとのORを取れば、情報を両方持つ事ができます。つまり、
from math import ceil,log2
def calc(nums):
shift=int(ceil(log2(len(nums))))
mask=2**shift-1
for i,num in enumerate(nums):
nums[i]=((nums[num]&mask)<<shift)|num
for i,num in enumerate(nums):
nums[i]=num>>shift
return numsとしても解くことができます。この手法が使える最大配列サイズも、2^96までで、Mediumの手法と変わりません。インポートやビット演算が必要でやや手間がかかるのが難点です。あまりメリットは無いですが、冗長ビットの利用というコンセプトは直接的に表現されていますね。この方法でサブしてみた結果を貼ります。
結論
「定数メモリ」で問題を解く際にこの手法が役立てば幸いです。
コメント