在 Python 中查詢前 N 個自然數排列中中位數為 M 的子陣列個數

假設我們有一個數組 A，包含前 N 個自然數的排列，並且還給定另一個數字 M，其中 M ≤ N，我們需要找到中位數為 M 的子陣列的個數。眾所周知，序列的中位數定義為按升序排序後位於序列中間的元素的值。對於偶數長度的序列，使用兩個中間元素中的左側元素。

因此，如果輸入類似於 A = [3, 5, 6, 4, 2] 且 M = 5，則輸出將為 4，因為所需的子陣列為 [3, 5, 6]、[5]、[5, 6] 和 [5, 6, 4]。

為了解決這個問題，我們將遵循以下步驟：

  • n := 陣列大小

  • my_map := 一個新的對映

  • my_map[0] := 1

  • has := False，add := 0，result := 0

  • 對於 i 從 0 到 n，執行：

    • 如果 arr[i] < m，則

      • add := add - 1

    • 否則，如果 arr[i] > m，則

      • add := add + 1

    • 如果 arr[i] 等於 m，則

      • has := True

    • 如果 has 為真，則

      • 如果 my_map 中存在 add，則

        • result := result + my_map[add]

      • 如果 my_map 中存在 add - 1，則

        • result := result + my_map[add - 1]

    • 否則，

      • my_map[add] := (如果存在 my_map[add] 的值，則為該值，否則為 0) + 1

  • 返回 result

示例

讓我們看看下面的實現，以便更好地理解：

 線上演示

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

更新於：2020年8月27日

266 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告