檢查 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 次瀏覽

啟動您的 職業生涯

完成課程獲得認證

開始