โปรแกรมหาความต่างดัชนีขั้นต่ำของสมาชิกติดกันในค่าที่เรียงแล้วใน Python

ได้รับลิสต์ nums สองตัวเลข nums[i] ≤ nums[j] เรียกว่า "ติดกัน" (adjacent) ถ้า ไม่มีตัวเลขอื่นอยู่ระหว่างค่าของพวกเขาในอาเรย์ หา |j-i| น้อยที่สุดของคู่ที่ติดกันนี้

ตัวอย่าง

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

Output: 2

คู่ติดกันในค่า: (1,2), (-9,-6), (-6,1), (2,6) → ดัชนีห่างน้อยสุดคือ 2 และ 6 (index 2 และ 4)

แนวทางแก้ปัญหา

1. จัดกลุ่ม index ของแต่ละค่า → indexes[value] = [indices...]
2. ในกลุ่มเดียวกัน: หา min(index[i+1] - index[i])
3. ระหว่างค่าที่ติดกันใน sorted order: ใช้ two-pointer หา min(|i-j|) ระหว่างสองกลุ่ม index

การใช้งาน (Python)

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 indices in indexes.values():
            for i in range(len(indices) - 1):
                ans = min(ans, indices[i + 1] - indices[i])
        
        # คู่ค่าที่ติดกันใน sorted order
        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()
print(ob.solve([1, -9, 6, -6, 2]))  # Output: 2

ความซับซ้อน

• Time Complexity: O(N log N) (จากการ sort distinct values)
• Space Complexity: O(N)