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

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

इसलिए, यदि इनपुट संख्या =[1, -9, 6, -6, 2] की तरह है, तो आउटपुट 2 होगा, जैसा कि हम देख सकते हैं कि 2 और 6 आसन्न हैं और वे एक दूसरे से 2 सूचकांक दूर हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• अनुक्रमणिका :=एक नया नक्शा

• प्रत्येक अनुक्रमणिका i और मान x के लिए A, करें

  • अनुक्रमणिका के अंत में i डालें[x]

• Ans :=A का आकार

• अनुक्रमणिका के सभी मानों की सूची में प्रत्येक पंक्ति के लिए, करें

  • मैं के लिए 0 से लेकर पंक्ति - 2 के आकार तक, करें

    • उत्तर:=न्यूनतम उत्तर और (पंक्ति [i + 1] - पंक्ति [i])

• vals :=सूची अनुक्रमणिका को क्रमबद्ध करें

• कश्मीर के लिए 0 से लेकर वैल - 2 के आकार तक, करें

  • r1 :=अनुक्रमणिका[vals[k]]

  • r2 :=अनुक्रमणिका[vals[k + 1]]

  • मैं :=j :=0

  • जबकि i

    • उत्तर:=न्यूनतम उत्तर और |r1[i] - r2[j]|

    • अगर r1[i]

      • मैं :=मैं + 1

    • अन्यथा,

      • जे:=जे + 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