Pythonで少なくとも1つの一意の要素を含むリスト内のすべてのサブリストをチェックするプログラム

numsという要素のリストがあるとすると、すべてのサブリストに、サブリストに1回だけ出現する要素が少なくとも1つ含まれているかどうかを確認する必要があります。この問題を線形時間で解決する必要があります。

したがって、入力がnums =[5、10、20、10、0]のような場合、numsのすべてのサブリストには1回だけ発生した要素が少なくとも1つあるため、出力はTrueになります。 [[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の要素が少なくとも1つあります。

これを解決するには、次の手順に従います-

• 関数has_unique（）を定義します。これは左、右になります
• 左>=右の場合、
  • Trueを返す
• counts：=numsに存在する各要素の頻度を含む辞書[インデックスの左から右へ]
• カウント>1の最小頻度の場合、
  • Falseを返す
• 開始：=左
• 左から右の範囲のインデックスについては、
  • counts [nums [index]]が1と同じ場合、
    • has_unique（start、index-1）がfalseの場合、
      • Falseを返す
    • start：=index + 1
• return has_unique（start、right）
• mainメソッドから、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