পাইথনে সন্নিহিত উপাদানগুলির সূচকের ন্যূনতম সম্ভাব্য পার্থক্য খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার সংখ্যার একটি তালিকা আছে, আমরা বলতে পারি যে দুটি সংখ্যা 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]

• উত্তর :=A

  এর আকার

• ইনডেক্সের সমস্ত মানের তালিকার প্রতিটি সারির জন্য, করুন

  • আমি 0 থেকে সারির আকার - 2 এর মধ্যে, কর

    • উত্তর :=সর্বনিম্ন উত্তর এবং (সারি[i + 1] - সারি[i])

• vals :=তালিকা সূচী সাজান

• k-এর জন্য রেঞ্জ 0 থেকে vals - 2, do

  • r1 :=সূচী [vals[k]]

  • r2 :=সূচী [vals[k + 1]]

  • i :=j :=0

  • যখন i

    • উত্তর :=সর্বনিম্ন উত্তর এবং |r1[i] - r2[j]|

    • যদি r1[i]

      • i :=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