Chương trình tìm hiệu chỉ số nhỏ nhất của các phần tử liền kề giá trị trong Python

Cho danh sách nums. Hai số nums[i] <= nums[j] gọi là "liền kề giá trị" nếu không có số nào trong nums có giá trị nằm giữa chúng. Tìm min |j-i| của các cặp liền kề giá trị.

Ví dụ: [1, -9, 6, -6, 2] → 2 (cặp 2 và 6 cách nhau 2 chỉ số).

Giải thuật (Nhóm chỉ số theo giá trị + So sánh giá trị liền kề)

1. Gom chỉ số của mỗi giá trị vào indexes[val] (sorted tự nhiên do duyệt tuần tự).
2. Trong cùng một giá trị: cập nhật ans bằng khoảng cách chỉ số liên tiếp nhỏ nhất.
3. Sắp xếp các giá trị distinct → vals.
4. Với mỗi cặp giá trị liền kề vals[k], vals[k+1]: dùng 2 con trỏ duyệt 2 danh sách chỉ số đã sort để tìm |i-j| nhỏ nhất.

Ví dụ minh họa

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)
        # Cùng giá trị
        for row in indexes.values():
            for i in range(len(row) - 1):
                ans = min(ans, row[i + 1] - row[i])
        
        # Giá trị liền kề
        vals = sorted(indexes.keys())
        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))  # Output: 2

Đầu vào / Đầu ra

Input: [1, -9, 6, -6, 2]

Output: 2