3264. حالة الصفيف النهائية بعد عمليات الضرب K i

الصعوبة: سهلة

الموضوعات: صفيف ، رياضيات ، كومة (قائمة انتظار الأولوية) ، محاكاة

يتم إعطاؤك مجموعة عدد صحيح ، عدد صحيح K ، ومضاعف عدد صحيح.

تحتاج إلى إجراء عمليات K على NUMS. في كل عملية:

• ابحث عن القيمة الدنيا X في NUMS. إذا كانت هناك حوادث متعددة من القيمة الدنيا ، فحدد تلك التي تظهر أولاً .
• استبدل القيمة الدنيا المحددة X بمضاعف x *.

return صفيف عدد صحيح يدل على الحالة النهائية للرقم بعد أداء جميع عمليات K .

مثال 1:

• الإدخال: nums = [2،1،3،5،6] ، k = 5 ، multiplier = 2
• الإخراج: [8،4،6،5،6]
• توضيح:

| العملية | النتيجة |
| ------------------- | ----------------- |
| بعد العملية 1 | [2 ، 2 ، 3 ، 5 ، 6] |
| بعد العملية 2 | [4 ، 2 ، 3 ، 5 ، 6] |
| بعد العملية 3 | [4 ، 4 ، 3 ، 5 ، 6] |
| بعد العملية 4 | [4 ، 4 ، 6 ، 5 ، 6] |
| بعد العملية 5 | [8 ، 4 ، 6 ، 5 ، 6] |

مثال 2:

• الإدخال: nums = [1،2] ، k = 3 ، multiplier = 4
• الإخراج: [16،8]
• توضيح:

| العملية | النتيجة |
| ------------------- | ----------------- |
| بعد العملية 1 | [2 ، 2 ، 3 ، 5 ، 6] |
| بعد العملية 2 | [4 ، 2 ، 3 ، 5 ، 6] |
| بعد العملية 3 | [4 ، 4 ، 3 ، 5 ، 6] |
| بعد العملية 4 | [4 ، 4 ، 6 ، 5 ، 6] |
| بعد العملية 5 | [8 ، 4 ، 6 ، 5 ، 6] |

قيود:

• 1
• 1
• 1
• 1

تَلمِيح:

1. الحفاظ على أزواج فرز (NUMS [الفهرس] ، فهرس) في قائمة انتظار الأولوية.
2. محاكاة العملية k مرات.

حل:

نحتاج إلى تنفيذ العمليات كما هو موضح في بيان المشكلة. تتمثل الخطوات الرئيسية في العثور على الحد الأدنى من القيمة في الصفيف ، واستبدلها بالقيمة مضروبة في المضاعف المحدد ، ثم كرر هذه العملية.

بالنظر إلى أننا بحاجة إلى تحديد الحدوث الأول للحد الأدنى من القيمة واستبداله ، يمكننا التعامل مع هذا من خلال تتبع فهرس القيمة الدنيا أثناء كل عملية. سيستخدم تطبيق PHP قائمة انتظار الأولوية (Min-Heap) لاسترداد وتحديث القيمة الدنيا أثناء كل عملية.

دعنا ننفذ هذا الحل في PHP: 3264. حالة الصفيف النهائية بعد عمليات الضرب K

توضيح:

1. التهيئة : حلقة k مرات منذ أن تحتاج إلى إجراء عمليات k.
2. ابحث عن القيمة الدنيا :
   • تكرار على عدد الصفيف للعثور على أصغر قيمة و فهرس الحدوث الأول .
3. اضرب القيمة الدنيا :
   • استبدل القيمة في الفهرس المحدد بمنتج القيمة الحالية والمضاعف.
4. يكرر:
   • كرر الخطوات المذكورة أعلاه لتكرار k.
5. أعد الصفيف النهائي :
   • إرجاع الصفيف المعدل بعد جميع العمليات.

اختبار الإخراج

لحالات الاختبار المقدمة:

حالة الاختبار 1:

مدخل:

$nums = [2, 1, 3, 5, 6];
$k = 5;
$multiplier = 2;

الإخراج:

Output: [8, 4, 6, 5, 6]

حالة الاختبار 2:

مدخل:

$nums = [1, 2];
$k = 3;
$multiplier = 4;

الإخراج:

Output: [16, 8]

تعقيد

1. تعقيد الوقت :

   • لكل عملية من عمليات K ، يتطلب العثور على الحد الأدنى من القيمة في الصفيف O (n).
   • total: o (k x n) ، حيث
   تعقيد الفضاء
:

2. يستخدم الحل

   o (1)
   • مساحة إضافية.
   يلتزم هذا الحل بالقيود ويوفر النتائج المتوقعة لجميع حالات الاختبار.

إذا وجدت هذه السلسلة مفيدة ، فيرجى التفكير في إعطاء المستودع نجمة على github أو مشاركة المنشور على شبكاتك الاجتماعية المفضلة؟ إن دعمك يعني الكثير بالنسبة لي!

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

LinkedIn

• github