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

মনে করুন আমাদের একটি সংখ্যার তালিকা nums আছে, আমরা বলতে পারি দুটি সংখ্যা nums[i] ≤ nums[j] আছেনা যখন তাদের মাঝপথে (nums[i], nums[j]) তে nums-এ কোনো সংখ্যা নেই। আমাদের |j - i| এর ন্যূনতম সম্ভাব্য মান খুঁজে বের করতে হবে যাতে nums[j] এবং nums[i] আছেনা।

উদাহরণস্বরূপ, যদি ইনপুট হয় nums = [1, -9, 6, -6, 2], তবে আউটপুট হবে 2, কারণ আমরা দেখতে পাচ্ছি 2 এবং 6 আছেনা এবং তারা একে অপরের থেকে 2 সূচক দূরত্বে অবস্থিত।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

• indexes := একটি নতুন ম্যাপ

• A-এ প্রতিটি সূচক i এবং মান x এর জন্য, করুন

  • indexes[x]-এর শেষে i যোগ করুন

• ans := A-এর আকার

• indexes-এর সমস্ত মানের তালিকার প্রতিটি row-এর জন্য, করুন

  • i = 0 থেকে row-এর আকার - 2 পর্যন্ত, করুন

    • ans := ans এবং (row[i + 1] - row[i])-এর ন্যূনতম

• vals := indexes-এর তালিকা সাজান

• k = 0 থেকে vals-এর আকার - 2 পর্যন্ত, করুন

  • r1 := indexes[vals[k]]

  • r2 := indexes[vals[k + 1]]

  • i := j := 0

  • যখন i < r1-এর আকার এবং j < r2-এর আকার, করুন

    • ans := ans এবং |r1[i] - r2[j]|-এর ন্যূনতম

    • যদি r1[i] < r2[j], তবে

      • i := i + 1

    • অন্যথায়,

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