पायथन में आसन्न तत्वों के सूचकांकों के न्यूनतम संभावित अंतर ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। हम कह सकते हैं कि दो संख्याएं nums[i] <= nums[j] आसन्न हैं जब nums में (nums[i], nums[j]) के बीच कोई संख्या नहीं है। हमें न्यूनतम संभव |j-i| ज्ञात करना है जैसे कि nums[j] और nums[i] आसन्न हैं।

उदाहरण के लिए, nums = [1, -9, 6, -6, 2] के लिए आउटपुट 2 होगा (2 और 6 आसन्न हैं और 2 सूचकांक दूर हैं)।

एल्गोरिदम

• indexes := मान से सूचकांकों की सूची का मैप
• ans := len(A)
• समान मानों के लिए, लगातार सूचकांकों का न्यूनतम अंतर लें
• vals := सॉर्ट किए गए अद्वितीय मान
• लगातार मानों vals[k] और vals[k+1] के लिए, दो-पॉइंटर का उपयोग करके उनके सूचकांकों के बीच न्यूनतम निरपेक्ष अंतर ज्ञात करें
• ans वापस करें

उदाहरण

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