Python의 요소 목록에서 중복 항목을 찾는 프로그램

<시간/>

크기가 n + 1인 숫자라는 요소 목록이 있다고 가정하고 1, 2, ..., n 범위에서 선택합니다. 우리가 알고 있듯이, 비둘기집 원칙에 따라 중복이 있어야 합니다. 복제본을 찾아야 합니다. 여기서 우리의 목표는 O(n) 시간과 일정한 공간에서 작업을 찾는 것입니다.

따라서 입력이 nums =[2,1,4,3,5,4]와 같으면 출력은 4

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

q :=숫자에 있는 모든 요소의 합
n :=숫자 크기
v :=((n - 1)*(n)/2)
의 바닥
리턴 q - v

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(nums):
   q = sum(nums)
   n = len(nums)
   v = (n - 1) * (n) // 2
   return q - v

nums = [2,1,4,3,5,4]
print(solve(nums))

입력

[2,1,4,3,5,4]