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

PythonでO（n）時間とO（1）余分なスペースで最大繰り返し数を見つけます

配列内の要素が0からk-1の範囲にある場合、サイズnの配列があるとします。ここで、kは正の整数として表され、k<=nです。この配列で最大繰り返し数を見つける必要があります。

したがって、入力がk=8およびA=[3、4、4、6、4、5、2、8]の場合、出力は4になります。

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

  • n：=Aのサイズ

  • 0からnの範囲のiの場合、実行

    • A [A [i] mod k]：=A [A [i] mod k] + k

  • max_val：=A [0]

  • 結果：=0

  • 1からnの範囲のiの場合、実行します

    • A [i]> max_valの場合、

      • max_val：=A [i]

      • 結果：=i

  • 結果を返す

例

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

def get_max_repeating(A, k):
   n = len(A)
   for i in range(n):
      A[A[i]%k] += k
   max_val = A[0]
   result = 0
   for i in range(1, n):
      if A[i] > max_val:
         max_val = A[i]
         result = i
   return result
A = [3, 4, 4, 6, 4, 5, 2, 8]
k = 8
print(get_max_repeating(A, k))

入力

[3, 4, 4, 6, 4, 5, 2, 8], 8

出力

4

  1. PythonでO（n）時間とO（1）空間でBSTの中央値を見つける

    二分探索木（BST）があるとすると、その中央値を見つける必要があります。偶数のノードの場合、中央値=（（n / 2番目のノード+（n + 1）/ 2番目のノード）/ 2奇数のノードの場合、中央値=（n + 1）/2番目のノードです。 したがって、入力が次のような場合 その場合、出力は7になります これを解決するには、次の手順に従います- rootがNoneと同じ場合、 0を返す node_count：=ツリー内のノードの数 count_curr：=0 現在：=ルート currentがnullでない場合は、実行してください curren

  2. リスト内の最小数を見つけるPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −リストが表示されます。リストで利用可能な最小の番号を表示する必要があります ここでは、リストを並べ替えて最小の要素を取得するか、組み込みのmin（）関数を使用して最小の要素を取得できます。 次に、以下の実装の概念を観察しましょう- 例 list1 = [101, 120, 104, 145, 99] # sorting using built-in function list1.sort() print("Smallest element is:", list1[0]) 出力 Smal