Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonのスナップショット配列

次のインターフェイスをサポートするSnapshotArrayを実装する必要があるとします-

  • SnapshotArray（int length）これにより、指定された長さで配列のようなデータ構造が初期化されます。最初は、各要素は0に等しくなります。

  • set（index、val）これにより、指定されたインデックスの要素がvalと等しくなるように設定されます。

  • snap（）は配列のスナップショットを取得し、snap_idを返します。snap（）を呼び出した合計回数から1を引いたものです。

  • get（index、snap_id）これは、指定されたsnap_idでスナップショットを取得した時点で、指定されたインデックスの値を返します

したがって、配列サイズが2の場合、[0、5]を使用して設定され、その後スナップを取得して0を返し、[0、6]を使用して設定し、get（0、0）を使用してこれを返します。 5.

これを解決するには、次の手順に従います-

  • 初期化メソッドは次のようになります-

  • 現在：=0

  • arr：=長さの配列+1つの2次元配列の数[[0、0]]

  • set（）メソッドは-

    のようになります

  • temp：=arr [index]

    の最後の要素

  • temp [0] =currentの場合、arr [index]の最後の要素からのインデックス1の要素：=val

  • それ以外の場合は、[current、val]をarr [index]

    に挿入します

  • snap（）メソッドは次のようになります-

  • 電流を1増やし、カウントより1少ない値を返します

  • get（）メソッドは次のようになります-

  • temp：=arr [index]、low：=0、high：=tempの長さ– 1

  • 低<高

    • 中：=低+（高–低）/ 2

    • temp [mid、0] <=snap_idの場合、low：=mid、それ以外の場合、high：=mid – 1

  • 戻り温度[low、1]

例（Python）

理解を深めるために、次の実装を見てみましょう-

class SnapshotArray(object):
   def __init__(self, length):
      self.current = 0
      self.arr = [[[0,0]] for i in range(length+1)]
   def set(self, index, val):
      temp = self.arr[index][-1]
      #print(temp)
      if temp[0] == self.current:
         self.arr[index][-1][1] = val
      else:
         self.arr[index].append([self.current,val])
   def snap(self):
      self.current+=1
      return self.current -1
   def get(self, index, snap_id):
      temp = self.arr[index]
      low = 0
      high = len(temp)-1
      while low < high:
         mid = low + (high - low+1 )//2
         if temp[mid][0]<=snap_id:
            low = mid
         else:
            high = mid -1
      return temp[low][1]
ob = SnapshotArray(3)
ob.set(0,5)
print(ob.snap())
ob.set(0,6)
print(ob.get(0,0))

入力

Initialize the array using 3, then call set(0,5), snap(), set(0,6), get(0, 0)

出力

0
5

  1. Pythonで配列を回転

    配列Aがあるとします。kステップ右に回転する必要があります。したがって、配列がA =[5、7、3、6、8、1、5、4]、およびk =3の場合、出力は[1,5,4,5,7,3,6、 8]。手順は次のようなものです [4,5,7,3,6,8,1,5] [5,4,5,7,3,6,8,1] [1,5,4,5,7,3,6,8] これを解決するために、次の手順に従います。 nは配列のサイズです k =k mod n A =n –kからendまでのAのサブアレイ+0からn– k –1までのAのサブアレイ 理解を深めるために、次の実装を見てみましょう- 例 class Solut

  2. ソートされた配列をPythonでマージ

    2つの並べ替えられた配列AとBがあるとします。それらをマージして、1つの並べ替えられた配列Cのみを形成する必要があります。リストのサイズは異なる場合があります。 たとえば、A=[1,2,4,7]およびB=[1,3,4,5,6,8]とすると、マージされたリストCは[1,1,2,3,4、 4,5,6,7,8] これを解決するには、次の手順に従います- ifine i：=0、j：=0 and end：=length of A – 1 =0であり、A[end]ではありません。 end：=end – 1 whilej