719. أوجد K-th أصغر مسافة زوجية

الصعوبة: صعب

المواضيع: المصفوفة، المؤشران، البحث الثنائي، الفرز

يتم تعريف مسافة زوج من الأعداد الصحيحة a وb على أنها الفرق المطلق بين a وb.

نظرًا لمصفوفة أعداد صحيحة وعدد صحيح k، قم بإرجاع k^th أصغر مسافة بين جميع الأزواج nums[i] وnums[j] حيث 0 .

مثال 1:

• الإدخال: الأعداد = [1,3,1]، k = 1
• الإخراج: 0
• الشرح: هنا جميع الأزواج:

  (1,3) -> 2
  (1,1) -> 0
  (3,1) -> 2

ثم 1^st أصغر زوج مسافة هو (1,1)، ومسافته هي 0.

مثال 2:

• الإدخال: الأعداد = [1,1,1]، k = 2
• الإخراج: 0

مثال 3:

• الإدخال: الأعداد = [1,6,1]، ​​k = 3
• الإخراج: 5

قيود:

• n == الأعداد.طول
• 2
0 61

تَلمِيح:

بحث ثنائي عن الإجابة. كيف يمكنك التحقق من عدد الأزواج التي لها مسافة

حل:

يمكننا استخدام مزيج من البحث الثنائي وتقنية المؤشرين. إليك طريقة خطوة بخطوة لحل هذه المشكلة:

يقترب:

1. فرز المصفوفة: أولاً، قم بفرز أرقام المصفوفة. يساعد الفرز في حساب عدد الأزواج بكفاءة بمسافة أقل من أو تساوي قيمة معينة.

2. البحث الثنائي عن المسافة : استخدم البحث الثنائي للعثور على أصغر مسافة k-th. تتراوح مساحة البحث عن المسافات من 0 (أصغر مسافة ممكنة) إلى max(nums) - min(nums) (أكبر مسافة ممكنة).

3. حساب الأزواج بمسافة ≥ منتصف : لكل قيمة متوسطة في البحث الثنائي، قم بحساب عدد الأزواج بمسافة أقل من أو تساوي المنتصف. ويمكن القيام بذلك بكفاءة باستخدام نهج المؤشرين.

4. ضبط نطاق البحث الثنائي: اعتمادًا على عدد الأزواج ذات المسافة الأقل أو المساوية للمنتصف، اضبط نطاق البحث الثنائي. إذا كان العدد أقل من k، قم بزيادة الحد الأدنى؛ وإلا قم بتقليل الحد الأعلى.

لننفذ هذا الحل بلغة PHP:

719. أوجد أصغر مسافة زوجية من K-th

توضيح:

• countPairsWithDistanceLessThanOrEqualTo: تحسب هذه الدالة عدد الأزواج التي لها مسافة أقل من أو تساوي المنتصف. ويستخدم مؤشرين، حيث اليمين هو العنصر الحالي، ويتم ضبط اليسار حتى يكون الفرق بين الأعداد [يمين] والأعداد [يسار] أقل من أو يساوي المنتصف.

• smallestDistancePair: تستخدم هذه الوظيفة البحث الثنائي للعثور على أصغر مسافة k-th. تحدد القيم المنخفضة والعالية نطاق البحث الحالي للمسافات. يتم التحقق من القيمة المتوسطة باستخدام الدالة countPairsWithDistanceLessThanOrEqualTo. واعتماداً على النتيجة يتم تعديل مساحة البحث.

تعثر هذه الخوارزمية بكفاءة على أصغر مسافة زوجية من k مع تعقيد زمني قدره O(n log(max(nums) - min(nums)) n log n).

روابط الاتصال

إذا وجدت هذه السلسلة مفيدة، فيرجى التفكير في منح

المستودع نجمة على GitHub أو مشاركة المنشور على شبكات التواصل الاجتماعي المفضلة لديك؟. دعمكم سيعني الكثير بالنسبة لي!

إذا كنت تريد المزيد من المحتوى المفيد مثل هذا، فلا تتردد في متابعتي:

• لينكد إن
• جيثب