Pythonで中央値がMになるように、最初のN個の自然数の順列でサブ配列の数を見つけます

最初のN個の自然数の順列を含む配列Aがあり、別の数Mも与えられていると仮定します。ここで、M≤Nの場合、次のようなサブ配列の数を見つける必要があります。シーケンスの中央値はMです。ご存知のように、シーケンスの中央値は、昇順で並べ替えた後のシーケンスの中央にある要素の値として定義されます。偶数の長さのシーケンスでは、2つの中央の要素の左側が使用されます。

したがって、入力がA =[3、5、6、4、2]およびM =5の場合、必要なサブ配列は[3、5、6]、[5]、[5]であるため、出力は4になります。 、6]および[5、6、4]。

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

• n：=arrのサイズ

• my_map：=新しいマップ

• my_map [0]：=1

• ：=False、追加：=0、結果：=0

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

  • arr [i]

    • 追加：=追加-1

  • それ以外の場合、arr [i]> mの場合、

    • 追加：=追加+ 1

  • arr [i]がmと同じ場合、

    • 持っている：=True

  • hasがtrueの場合、

    • my_mapに存在を追加する場合は、

      • 結果：=結果+ my_map [add]

    • add-1がmy_mapに存在する場合、

      • 結果：=結果+ my_map [add-1]

  • それ以外の場合

    • my_map [add]：=（my_map [add]の値（存在する場合は0）+ 1

• 結果を返す

例

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

def solve(arr, m):
   n = len(arr)
   my_map = {}
   my_map[0] = 1
   has = False
   add = 0
   result = 0
   for i in range(n):
      if (arr[i] < m):
         add -= 1
      elif (arr[i] > m):
         add += 1
      if (arr[i] == m):
         has = True
      if (has):
         if(add in my_map):
            result += my_map[add]
         if add-1 in my_map:
            result += my_map[add - 1]
      else:
         my_map[add] = my_map.get(add, 0) + 1
   return result
arr = [3, 5, 6, 4, 2]
m = 5
print(solve(arr, m))

入力

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

出力

3