Python程式檢查列表中每個子列表是否至少包含一個唯一元素

假設我們有一個名為nums的元素列表，我們需要檢查每個子列表中是否至少有一個元素只在該子列表中出現一次。我們需要線上性時間內解決此問題。

因此，如果輸入類似於nums = [5, 10, 20, 10, 0]，則輸出將為True，因為nums中的每個子列表都至少有一個元素只出現一次。[[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0]]都至少有一個頻率為1的元素。

為了解決這個問題，我們將遵循以下步驟 -

• 定義一個函式has_unique()。這將接收left、right作為引數
• 如果left >= right，則
  • 返回True
• counts := 一個字典，包含nums[從索引left到right]中每個元素的頻率
• 如果counts中的最小頻率 > 1，則
  • 返回False
• start := left
• 對於從left到right的索引範圍，執行以下操作
  • 如果counts[nums[index]]等於1，則
    • 如果has_unique(start, index - 1)為false，則
      • 返回False
    • start := index + 1
• 返回has_unique(start, right)
• 從主方法返回has_unique(0, nums的大小 - 1)

示例

讓我們看看以下實現以更好地理解 -

from collections import Counter
def solve(nums):
   def has_unique(left, right):
      if left >= right:
         return True

      counts = Counter(nums[left : right + 1])
      if min(counts.values()) > 1:
         return False

      start = left

      for index in range(left, right + 1):
         if counts[nums[index]] == 1:
            if not has_unique(start, index - 1):
               return False
            start = index + 1

      return has_unique(start, right)

   return has_unique(0, len(nums) - 1)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

輸入

[5, 10, 20, 10, 0]

輸出

True

Arnab Chakraborty

更新於: 2021年10月18日

243 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

立即開始