Count Inversions
معطاة قائمة من الأعداد الصحيحة nums، أعد عدد الانقلابات: أزواج الفهارس i < j التي يكون فيها nums[i] > nums[j]، أي قيمة أكبر تسبق قيمة أصغر. القيم المتساوية لا تشكّل انقلابًا أبدًا، والقائمة المرتبة لا تحتوي على أي انقلاب.
الدالة
- numsinteger-array
- قائمة الأعداد الصحيحة
- تُرجعinteger
- عدد الأزواج i < j التي تحقق nums[i] > nums[j]
القيود
1 ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- الإجابة لا تتجاوز
n(n-1)/2 < 2 × 108، لذا فهي تناسب عددًا صحيحًا موقّعًا من 32 بت.
أمثلة
- المدخلات
- nums = [5, 3, 8, 1, 4]
- المخرجات
- 6
- الشرح
- يأتي 5 قبل 3 و1 و4: 3 أزواج. يأتي 3 قبل 1، ويأتي 8 قبل 1 و4: 3 أزواج أخرى. 1 و4 بالترتيب، لذا فالمجموع 6.
- المدخلات
- nums = [2, 2, 2, 1]
- المخرجات
- 3
- الشرح
- كل واحد من الأعداد 2 الثلاثة يأتي قبل العدد 1، لذا توجد 3 أزواج معكوسة. ولا يُحتسب العددان 2 المتساويان، لأن الزوج المعكوس يتطلب أن تكون القيمة الأولى أكبر بشكل صارم.
- المدخلات
- nums = [-1, 0, 7, 7]
- المخرجات
- 0
- الشرح
- القائمة مرتبة، والعددين 7 المتساويين لا يُحتسبان، لذا الإجابة هي 0.
سؤال إضافي
ما الذي يتغير إذا احتُسب الزوج فقط عندما يكون nums[i] > 2 × nums[j]؟ هل لا يزال بإمكان فرز الدمج احتساب هذه الأزواج في O(n log n)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
قسّم القائمة إلى نصف أيسر ونصف أيمن. كل انقلاب يقع داخل النصف الأيسر، أو داخل النصف الأيمن، أو يكون زوجًا يحتوي على قيمة من كل جانب. هل يمكنك عدّ المجموعات الثلاث كلٌّ على حدة؟
ترتيب كل نصف لا يغيّر عدد الأزواج التي تعبر الوسط، لأن كل قيمة في النصف الأيسر تظل إلى يسار كل قيمة في النصف الأيمن. وعندما يكون النصفان مرتّبين، يمكنك عدّ الأزواج العابرة على دفعات بدلًا من عدّها واحدًا تلو الآخر.
استخدم الترتيب بالدمج. أثناء دمج نصفين مرتبين، في كل مرة تأخذ فيها قيمة من النصف الأيمن، تكون أصغر من كل قيمة ما زالت في انتظار المعالجة في النصف الأيسر، لذا أضف عدد القيم المتبقية فيه. خذ القيمة من النصف الأيسر عند التعادل، حتى لا تُحتسب القيم المتساوية أبدًا.
الحل
تتطلب مقارنة كل زوج نحو n² / 2 مقارنة. يحصي الفرز بالدمج الأزواج دفعةً واحدة: عندما تُوضَع قيمة من النصف الأيمن أثناء الدمج، تكون كل قيمة لا تزال في انتظارها من النصف الأيسر أكبر منها، وقد سبقتها. وتكفي عملية طرح واحدة لاحتساب هذه المجموعة بأكملها، لذا لا يضيف العد أي تكلفة تتجاوز تكلفة الفرز O(n log n).
تحقّق من كل زوج
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
لكل فهرس i، تحقّق من كل فهرس لاحق j وأضف 1 عندما يكون nums[i] > nums[j]. هذا هو التعريف، والمقارنة الصارمة تستثني القيم المتساوية.
تبلغ الكلفة n(n-1)/2 مقارنة: ما يقارب 2 × 10^8 مقارنة لـ 2 × 10^4 قيمة، ومضاعفة n تجعلها أكبر بأربعة أضعاف.
الخوارزمية
- عيّن
count = 0. - لكل
iمن 0 إلىn-1، ولكلjمنi + 1إلىn-1، أضف 1 إلىcountعندما يكونnums[i] > nums[j]. - أعِد
count.
def countInversions(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] > nums[j]:
count += 1
return countالترتيب بالدمج مع العدّ أثناء الدمج
الفكرة
قسّم القائمة من المنتصف. يكون كلا العنصرين في الانعكاس في النصف الأيسر، أو كلاهما في النصف الأيمن، أو يكون أحدهما في كل جانب. يحصي الاستدعاء العودي على كل نصف النوعين الأولين ويرتّب ذلك النصف. لا ينقل الترتيب القيم إلا داخل النصف، لذا تظل كل قيمة يسرى سابقة لكل قيمة يمنى، وتبقى الأزواج العابرة دون تغيير.
أثناء الدمج، إذا كان left[i] ≤ right[j]، فضع left[i]: كل قيمة يمنى ما زالت تنتظر لا تقل عن right[j]، لذا لا تكوّن أي انعكاس. وإلا، تكون right[j] أصغر من left[i]، وبما أن النصف الأيسر مرتب، فهي أصغر من كل قيمة يسرى ما زالت تنتظر. أضف عددها. وضع القيمة اليسرى عند التعادل يُبقي القيم المتساوية خارج الانعكاسات.
في [5, 3, 8, 1, 4]، يحتوي النصفان على انعكاس واحد وانعكاسين. عند دمج [3, 5] مع [1, 4, 8]، تتجاوز 1 القيمتين 3 و5، وتتجاوز 4 القيمة 5: 1 + 2 + 3 = 6.
الخوارزمية
- انسخ
numsوأنشئ مخزنًا مؤقتًا بالطول نفسه. - لترتيب نطاق يحتوي على أقل من قيمتين وعدّها، أرجع 0.
- وإلا، فقسّمه عند
midورتّب كل نصف وعدّ عناصره. - ادمج النصفين عبر المخزن المؤقت: إذا كان
left[i] ≤ right[j]فخذ القيمة اليسرى؛ وإلا فخذ القيمة اليمنى وأضف عدد القيم اليسرى التي لم توضع بعد. - انسخ النطاق المدمج إلى موضعه الأصلي وأرجع مجموع الأعداد الثلاثة.
def sortAndCount(a, buf, lo, hi):
# Sorts a[lo:hi] and returns the number of inversions inside it.
if hi - lo < 2:
return 0
mid = (lo + hi) // 2
count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
# Merge the two sorted halves, counting the pairs that cross the middle.
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
buf[k] = a[i]
i += 1
else:
# a[j] is smaller than every left value not placed yet: a[i..mid-1].
buf[k] = a[j]
j += 1
count += mid - i
k += 1
while i < mid:
buf[k] = a[i]
i += 1
k += 1
while j < hi:
buf[k] = a[j]
j += 1
k += 1
a[lo:hi] = buf[lo:hi]
return count
def countInversions(nums):
a = list(nums) # sort a copy, not the caller's list
return sortAndCount(a, [0] * len(a), 0, len(a))
أخطاء شائعة وحالات حدّية
- إضافة 1 عند وضع قيمة من النصف الأيمن. فهي تتجاوز كل قيمة من النصف الأيسر لا تزال قيد الانتظار، لذا أضف عددها،
mid - i. - اختيار القيمة من النصف الأيمن عند التعادل، باستخدام
left[i] < right[j]شرطًا لاختيار القيمة من النصف الأيسر. عندها تحسب[2, 2, 2, 1]قيم 2 المتساوية بعضها مقابل بعض، وتُرجع نتيجة أكبر من 3. استخدم≤. - العد أثناء نسخ القيم المتبقية بعد نفاد أحد النصفين. لا توجد قيمة من النصف الأيمن تأتي بعد القيم المتبقية من النصف الأيسر، أما القيم المتبقية من النصف الأيمن فقد سبق مقارنتها بكل قيمة من النصف الأيسر.
أسئلة شائعة3
ما هو الانعكاس في مصفوفة؟
الانقلاب هو زوج من المواضع i < j حيث nums[i] > nums[j]، أي إن قيمة أكبر تقع قبل قيمة أصغر. تحتوي القائمة المرتبة على 0 من الانقلابات، وتحتوي القائمة المعكوسة ذات القيم المميزة على أكبر عدد منها، n(n-1)/2. يساوي هذا العدد عدد عمليات تبديل العناصر المتجاورة التي تجريها خوارزمية الترتيب بالفقاعات.
ما هو التعقيد الزمني لعدّ الانقلابات باستخدام الفرز بالدمج؟
زمن O(n log n) ومساحة إضافية O(n) لمخزن الدمج. يلامس كل مستوى من مستويات الدمج البالغ عددها log n كل قيمة مرة واحدة، أي نحو 3 × 10^5 خطوة لـ 2 × 10^4 قيمة. أما الحلقة التي تعالج الأزواج واحدًا تلو الآخر فتعقيدها O(n²).
هل يمكن حساب الانقلابات دون استخدام الترتيب بالدمج؟
نعم. شجرة Fenwick (الشجرة المفهرسة ثنائيًا) على رتب القيم تمرّ على القائمة مرة واحدة، وتسأل، لكل قيمة، عن عدد القيم السابقة الأكبر منها، بتعقيد O(log n) لكل قيمة. وهذا أيضًا بتعقيد إجمالي O(n log n). وتعمل شجرة بحث متوازنة تتتبّع أحجام الأشجار الفرعية بالطريقة نفسها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def countInversions(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [5, 3, 8, 1, 4]
الإخراج المتوقع
6