𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
تطلب منك مسألة Leetcode 169 إيجاد العنصر الأكثر تكراراً (majority element) في مصفوفة. يظهر هذا العنصر أكثر من n / 2 من المرات. ونفترض أنه موجود دائماً.
يمكنك حل هذه المسألة بطريقتين.
الطريقة الأولى: استخدام الخريطة (Map Method)
تستخدم هذه الطريقة خريطة (Map) لحساب عدد مرات ظهور كل رقم.
- إنشاء خريطة (Map) لتخزين التكرارات.
- المرور عبر المصفوفة (Loop).
- تحديث عدد التكرارات لكل رقم.
- المرور عبر الخريطة للعثور على الرقم الذي يتجاوز تكراره n / 2.
التعقيد (Complexity):
- الوقت: O(n) لأنك تستخدم حلقتين متتاليتين.
- المساحة: O(n) لأن حجم الخريطة يزداد مع زيادة عدد العناصر الفريدة.
الطريقة الثانية: خوارزمية Boyer-Moore للتصويت (Boyer-Moore Voting Algorithm)
هذه طريقة محسنة لحل المسألة باستخدام مساحة ذاكرة ثابتة.
تخيل الأرقام كفرق متنافسة. في كل مرة يلتقي فيها رقم برقم مختلف، فإنهما يلغيان بعضهما البعض. وبما أن العنصر الأكثر تكراراً يظهر أكثر من نصف الوقت، فسيكون هو دائماً العنصر الأخير المتبقي.
آلية العمل:
- اختر مرشحاً (candidate) واجعل العداد 0.
- المرور عبر المصفوفة.
- إذا كان العداد 0، اجعل الرقم الحالي هو المرشح.
- إذا كان الرقم الحالي يطابق المرشح، قم بزيادة العداد بمقدار 1.
- إذا لم يطابق المرشح، قم بتقليل العداد بمقدار 1.
التعقيد (Complexity):
- الوقت: O(n) لأنك تمر عبر المصفوفة مرة واحدة فقط.
- المساحة: O(1) لأنك تستخدم متغيرين فقط.
لماذا يهم هذا الأمر:
كلتا الطريقتين لهما تعقيد زمني قدره O(n). ومع ذلك، تستخدم الطريقة الثانية ذاكرة أقل بكثير، فهي لا تحتاج إلى خريطة (Map)، مما يجعلها أفضل للبيانات الضخمة.
المصدر: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6