파이썬에서 거리가 연속적이지 않은 가장 작은 쌍의 합을 찾는 프로그램

<시간/>

호출된 번호 목록이 있다고 가정합니다. 이제 i 1인 모든 인덱스 쌍(i, j)을 고려해 보겠습니다. 그런 다음 가장 작은 쌍의 합을 찾습니다.

따라서 입력이 nums =[3, 4, 2, 2, 4]와 같으면 출력은 5가 되고 값 3과 2를 선택할 수 있으므로 총합은 5가 됩니다. 2와 2는 선택할 수 없습니다. 인접하고 j - i> 1 제약 조건을 위반합니다.

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

n :=숫자 크기
min_seen :=nums[0]
ans :=inf
2 ~ n - 1 범위의 i에 대해 다음을 수행합니다.
- ans :=ans 및 (min_seen + nums[i])의 최소값
- min_seen :=min_seen 및 nums[i - 1]의 최소값
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(nums):
   n = len(nums)
   min_seen = nums[0]

   ans = float("inf")

   for i in range(2, n):
      ans = min(ans, min_seen + nums[i])

      min_seen = min(min_seen, nums[i - 1])
   return ans

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

입력

[3, 4, 2, 2, 4]