Python程序：查找大于给定值的集合数量

假设我们有一个包含多个整数的数组。我们找出该数字数组中所有连续的子数组，并将其放入另一个列表中。现在，我们将每个子数组替换为该子数组中的最大元素。我们还有一个给定的数字k，我们必须找出现在有多少个子数组大于该数字。

因此，如果输入类似于 input_array = [5, 6, 7, 8], k = 7，则输出将为4

给定输入数组的连续子数组为：{5}, {6}, {7}, {8}, {5, 6}, {6, 7}, {7, 8}, {5, 6, 7}, {6, 7, 8}, {5, 6, 7, 8}

如果我们用它们中的最大元素更新子数组，则子数组变为：

{5}, {6}, {7}, {8}, {6}, {7}, {8}, {7}, {8}, {8}.

有4个集合的元素大于7。

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

  • count := 0
  • consecutive := 0
  • 对于 input_array 中的每个 x，执行：
    • 如果 x > k，则
      • consecutive := 0
    • 否则，
      • consecutive := consecutive + 1
      • count := count + consecutive

返回 input_array 的大小 * ((input_array 的大小 + 1) / 2) 的向下取整值 - count

示例

让我们来看下面的实现，以便更好地理解：

在线演示

def solve(input_array, k):
   count = 0
   consecutive = 0
   for x in input_array:
      if x > k:
         consecutive = 0
      else:
         consecutive += 1
         count += consecutive
   return len(input_array) * (len(input_array) + 1) // 2 - count
print(solve([5, 6, 7, 8], 7))

输入

[5, 6, 7, 8], 7

输出

4

更新于：2021年5月18日

255 次浏览

开启您的职业生涯

通过完成课程获得认证

开始学习
广告