Chương trình lấy chỉ số của danh sách sau khi xóa phần tử theo thứ tự tăng dần trong Python

Cho danh sách các giá trị khác nhau. Xóa các số theo thứ tự không giảm (tăng dần). Trả về danh sách chỉ số của các phần tử bị xóa theo thứ tự xóa.

Ví dụ: nums = [4,6,2,5,3,1] → xóa 1 (chỉ số 5), mảng thành [4,6,2,5,3]; xóa 2 (chỉ số 2), mảng thành [4,6,5,3]; xóa 3 (chỉ số 3), ... → kết quả [5,2,3,0,1,0].

Giải thuật (Merge Sort đếm số phần tử lớn hơn bên trái)

Sử dụng Merge Sort biến đổi: khi trộn, nếu lấy phần tử từ nửa phải (giá trị nhỏ hơn), thì số phần tử còn lại ở nửa trái chính là số phần tử lớn hơn nó đứng trước nó trong mảng gốc. Cộng dồn vào mảng larger.

• Hàm my_sort(inds) sắp xếp chỉ số theo giá trị nums, đồng thời cập nhật larger.
• Sau khi sắp xếp, ghép cặp (nums[i], larger[i]), sắp xếp theo nums (thứ tự xóa), lấy larger theo thứ tự đó.

Mã nguồn Python

class Solution:
    def solve(self, nums):
        def my_sort(inds):
            if len(inds) <= 1:
                return inds
            mid = len(inds) // 2
            left, right = my_sort(inds[:mid]), my_sort(inds[mid:])
            i = j = 0
            sorted_inds = []
            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(list(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))  # Output: [5, 2, 3, 0, 1, 0]

Đầu vào

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

Đầu ra

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