检查 Python 中至少一半数组是否可以通过执行某些操作归约为零

假设我们得到一个包含正整数的长度为 n 的列表和另一个正整数 m。假设我们当前在一个循环中，每次迭代，我们将数组中某些元素的值减少 1，并将其余元素的值增加 m。我们必须找出在一些迭代之后，列表中是否有一半或更多元素变为零。如果可能，我们返回 True，否则返回 False。

因此，如果输入类似于 input_list = [10, 18, 35, 5, 12]，m = 4，则输出为 True。

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

• frequency_list := 一个大小为 m+1 并初始化为 0 的新列表
• i := 0
• 当 i < input_list 的大小 时，执行：

  • frequency_list[input_list[i] mod (m + 1)] :=

    frequency_list[input_list[i] mod (m + 1)] + 1

  • i := i + 1
• i := 0
• 当 i <= m 时，执行：
  • 如果 frequency_list[i] >= (input_list 的大小 / 2)，则
    • 退出循环
  • i := i + 1
• 如果 i <= m，则
  • 返回 True
• 否则，
  • 返回 False

示例

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

演示

def solve(input_list, m):
   frequency_list = [0] * (m + 1)
   i = 0
   while(i < len(input_list)):
      frequency_list[(input_list[i] % (m + 1))] += 1
      i += 1
   i = 0
   while(i <= m):
      if(frequency_list[i] >= (len(input_list)/ 2)):
         break
      i += 1
   if (i <= m):
      return True
   else:
      return False
input_list = [10, 18, 35, 5, 12]
print(solve(input_list, 4))

输入

[10, 18, 35, 5, 12], 4

输出

True

Arnab Chakraborty

更新于：2021年1月18日

69 次浏览

启动您的 职业生涯

完成课程获得认证

开始