在前N个自然数的置换中找到子数组的数目，以使其在Python中的中位数为M

假设我们有一个包含前N个自然数的排列的数组A，并且还给出了另一个数M，其中M≤N，我们必须找到子数组的数量，使得序列的中位数为M。序列的中位数定义为按升序对元素进行排序后位于序列中间的元素的值。对于偶数长度序列，使用两个中间元素的左侧。

因此，如果输入像A = [3，5，6，4，2]并且M = 5，则输出将是4，因为所需的子数组是[3，5，6]，[5]，[5 ，6]和[5，6，4]。

为了解决这个问题，我们将遵循以下步骤-

• n：= arr的大小

• my_map：=新映射

• my_map [0]：= 1

• 具有：= False，添加：= 0，结果：= 0

• 对于0到n范围内的i，执行

• my_map [add]：=（my_map [add]的值，如果存在，否则为0）+1

• 如果添加存在于my_map中，则

• 如果add-1存在于my_map中，则

• 结果：=结果+ my_map [添加]

• 结果：=结果+ my_map [添加-1]

• 具有：=真

• 加：=加+ 1

• 加：=加-1

• 如果arr [i] <m，则

• 否则，当arr [i]> m时，

• 如果arr [i]与m相同，则

• 如果has为真，则

• 除此以外，

• 返回结果

示例

让我们看下面的实现以更好地理解-

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