Python程序：删除元素后获取列表索引（升序删除）

假设我们有一个包含不同值的列表，我们希望按非递减顺序删除每个数字。我们必须找到按删除顺序排列的数字的索引。

因此，如果输入类似于 nums = [4, 6, 2, 5, 3, 1]，则输出将为 [5, 2, 3, 0, 1, 0]，因为我们删除 1，所以数组为 [4, 6, 2, 5, 3]，然后删除 2，数组为 [4, 6, 5, 3]，然后删除 3 我们得到 [4, 6, 5]，然后删除 4 我们得到 [6, 5]，删除 5，[6]，最后删除 6。

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数 my_sort()。这将接收 inds
• 如果 inds 的大小 <= 1，则
  • 返回 inds
• sorted_inds := 一个新的列表
• mid := inds 的大小 / 2
• left := my_sort(inds[从索引 0 到 mid])，right := my_sort(inds[从索引 mid 到结尾])
• i := 0，j := 0
• 当 i < left 的大小 且 j < right 的大小 时，执行
  • 如果 nums[left[i]] < nums[right[j]]，则
    • 将 left[i] 插入 sorted_inds 的末尾
    • i := i + 1
  • 否则，
    • 将 right[j] 插入 sorted_inds 的末尾
    • larger[right[j]] := larger[right[j]] + left 的大小 - i
    • j := j + 1
• 将 left[从索引 i 到结尾] 插入 sorted_inds
• 将 right[从索引 j 到结尾] 插入 sorted_inds
• 返回 sorted_inds
• 从主方法执行以下操作：
• larger := 一个大小为 nums 的新列表，并填充 0
• my_sort(范围 0 到 nums 的大小)
• num_larger_pairs := 为每个 (nums, larger) 创建对并排序它们
• 返回一个列表，其中包含所有 e in num_larger_pairs 的 e[1]

示例（Python）

让我们看看以下实现以更好地理解：

 在线演示

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]

Arnab Chakraborty

更新于：2020年12月12日

浏览量：143

开启你的职业生涯

完成课程获得认证

开始学习