Python에서 하나 이상의 고유한 요소를 포함하는 목록의 모든 하위 목록을 확인하는 프로그램

nums라는 요소 목록이 있다고 가정하고 모든 하위 목록에 해당 하위 목록에서 정확히 한 번 발생하는 최소 1개의 요소가 있는지 확인해야 합니다. 선형 시간에 이 문제를 해결해야 합니다.

따라서 입력이 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() 함수를 정의합니다. 왼쪽, 오른쪽
• 왼쪽>=오른쪽이면
  • 참 반환
• counts :=nums[인덱스 왼쪽에서 오른쪽으로]에 있는 각 요소의 빈도를 포함하는 사전
• 카운트의 최소 빈도> 1이면
  • 거짓을 반환
• 시작:=왼쪽
• 왼쪽에서 오른쪽 범위의 인덱스에 대해
  • counts[nums[index]]가 1과 같으면
    • has_unique(start, index - 1)가 거짓이면
      • 거짓을 반환
    • 시작 :=색인 + 1
• has_unique(start, right)를 반환
• 메인 메소드에서 has_unique(0, size of 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