โปรแกรมหาดัชนีของรายการหลังลบสมาชิกตามลำดับเพิ่มขึ้นใน Python

สมมติว่าเรามีรายการค่าที่ไม่ซ้ำกัน และต้องการลบตัวเลขแต่ละตัวตามลำดับไม่ลดลง (non-decreasing order) ต้องการหาดัชนีของตัวเลขในลำดับที่พวกเขาถูกลบ

เช่น nums = [4, 6, 2, 5, 3, 1] ผลลัพธ์ = [5, 2, 3, 0, 1, 0] ลบ 1 (ดัชนี 5) → [4,6,2,5,3] ลบ 2 (ดัชนี 2) → [4,6,5,3] ลบ 3 (ดัชนี 3) → [4,6,5] ลบ 4 (ดัชนี 0) → [6,5] ลบ 5 (ดัชนี 1) → [6] ลบ 6 (ดัชนี 0)

ขั้นตอนการแก้ปัญหา (Merge Sort + Count Larger Elements)

• ใช้ Merge Sort นับจำนวนสมาชิกที่มากกว่าและอยู่ทางซ้าย (inversion count แบบปรับเปลี่ยน)
• larger := array ขนาด n เติม 0
• ฟังก์ชัน my_sort(inds):
  • แบ่งครึ่ง เรียงซ้ายและขวา
  • merge: ถ้า nums[left[i]] < nums[right[j]] ใส่ left, มิฉะนั้น ใส่ right และ larger[right[j]] += len(left) - i
• เรียก my_sort(range(n))
• จับคู่ (nums[i], larger[i]) เรียงตาม nums คืน larger ตามลำดับนั้น

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums):
        return solve(nums)
def solve(nums):
    def my_sort(inds):
        if len(inds) <= 1:
            return inds
        sorted_inds = []
        mid = len(inds) // 2
        left, right = my_sort(inds[:mid]), my_sort(inds[mid:])
        i = j = 0
        while i < len(left) and j < len(right):
            if nums[left[i]] < nums[right[j]]:
                sorted_inds.append(left[i])
                i += 1
            else:
                sorted_inds.append(right[j])
                larger[right[j]] += len(left) - i
                j += 1
        sorted_inds.extend(left[i:])
        sorted_inds.extend(right[j:])
        return sorted_inds
    larger = [0] * len(nums)
    my_sort(range(len(nums)))
    num_larger_pairs = sorted(zip(nums, larger))
    return [e[1] for e in num_larger_pairs]

ob = Solution()
nums = [4, 6, 2, 5, 3, 1]
print(ob.solve(nums))

ข้อมูลนำเข้า

[4, 6, 2, 5, 3, 1]

ผลลัพธ์

[5, 2, 3, 0, 1, 0]