숫자 nums의 목록이 있다고 가정하고 nums의 (nums[i], nums[j]) 사이에 숫자가 없을 때 두 개의 숫자 nums[i] ≤ nums[j]가 인접한다고 말할 수 있습니다. 우리는 가능한 최소값을 찾아야 합니다 |j - i| nums[j]와 nums[i]가 인접하도록 합니다.
따라서 입력이 nums =[1, -9, 6, -6, 2]와 같으면 출력은 2가 됩니다. 2와 6은 인접하고 서로 2개의 인덱스 떨어져 있다는 것을 알 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
색인 :=새 지도
-
A의 각 인덱스 i와 값 x에 대해 수행
-
인덱스[x]의 끝에 i 삽입
-
-
as :=A의 크기
-
모든 인덱스 값 목록의 각 행에 대해
-
범위 0에서 행 크기 - 2에 있는 i의 경우 수행
-
ans :=ans의 최소값 및 (row[i + 1] - row[i])
-
-
-
vals :=목록 인덱스 정렬
-
범위 0에서 vals 크기 - 2의 k에 대해 수행
-
r1 :=인덱스[vals[k]]
-
r2 :=인덱스[vals[k + 1]]
-
나는 :=j :=0
-
동안 i
-
ans :=ans 및 |r1[i] - r2[j]|
의 최소값 -
r1[i]
-
나는 :=나는 + 1
-
-
그렇지 않으면
-
j :=j + 1
-
-
-
-
반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict class Solution: def solve(self, A): indexes = defaultdict(list) for i, x in enumerate(A): indexes[x].append(i) ans = len(A) for row in indexes.values(): for i in range(len(row) - 1): ans = min(ans, row[i + 1] - row[i]) vals = sorted(indexes) for k in range(len(vals) - 1): r1 = indexes[vals[k]] r2 = indexes[vals[k + 1]] i = j = 0 while i < len(r1) and j < len(r2): ans = min(ans, abs(r1[i] - r2[j])) if r1[i] < r2[j]: i += 1 else: j += 1 return ans ob = Solution() nums = [1, -9, 6, -6, 2] print(ob.solve(nums))
입력
[1, -9, 6, -6, 2]
출력
2