在 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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告