โปรแกรมค้นหาความแตกต่างขั้นต่ำที่เป็นไปได้ของดัชนีขององค์ประกอบที่อยู่ติดกันใน Python

สมมติว่าเรามีรายการตัวเลข 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 ดัชนี

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ดัชนี :=แผนที่ใหม่

• สำหรับแต่ละดัชนี i และค่า x ใน A ทำ

  • ใส่ i ต่อท้าย indexes[x]

• ans :=ขนาด A

• สำหรับแต่ละแถวในรายการค่าดัชนีทั้งหมด ทำ

  • สำหรับฉันในช่วง 0 ถึงขนาดของแถว - 2 ทำ

    • ans :=ขั้นต่ำของ ans และ (row[i + 1] - row[i])

• vals :=จัดเรียงดัชนีรายการ

• สำหรับ k ในช่วง 0 ถึงขนาดของ vals - 2 ทำ

  • r1 :=indexes[vals[k]]

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

  • ผม :=j :=0

  • ในขณะที่ฉัน <ขนาดของ r1 และ j <ขนาดของ r2 ให้ทำ

    • ans :=ขั้นต่ำของ ans และ |r1[i] - r2[j]|

    • ถ้า r1[i]

      • ผม :=ผม + 1

    • มิฉะนั้น

      • เจ :=เจ + 1

• กลับมาอีกครั้ง

ตัวอย่าง (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 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