标签: 贪心 树状数组 线段树 数组 二分查找 有序集合 排序
难度: Hard
给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作 直到数组为空 ：
请你返回需要多少个操作使 nums 为空。
示例 1：
输入：nums = [3,4,-1] 输出：5
| Operation | Array |
|---|---|
| 1 | [4, -1, 3] |
| 2 | [-1, 3, 4] |
| 3 | [3, 4] |
| 4 | [4] |
| 5 | [] |
示例 2：
输入：nums = [1,2,4,3] 输出：5
| Operation | Array |
|---|---|
| 1 | [2, 4, 3] |
| 2 | [4, 3] |
| 3 | [3, 4] |
| 4 | [4] |
| 5 | [] |
示例 3：
输入：nums = [1,2,3] 输出：3
| Operation | Array |
|---|---|
| 1 | [2, 3] |
| 2 | [3] |
| 3 | [] |
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 109nums 中的元素 互不相同 。运行时间: 135 ms
内存: 27.7 MB
class Solution:
def countOperationsToEmptyArray(self, nums: List[int]) -> int:
index = sorted(range(len(nums)), key=lambda k:nums[k])
total = len(index)
pre = 0
for i in range(len(index)):
if index[i] < pre:
total += len(index) - i
pre = index[i]
return total
题解利用了排序和索引来优化操作。首先，通过对数组元素的索引进行排序（基于它们的值），我们获得一个有序的索引列表，该列表直接指向数组中从最小值到最大值的元素。接下来，遍历这个有序索引列表，计算清空数组所需的总操作次数。对于每个元素，如果其索引小于前一个元素的索引（说明在原数组中，这个元素在前一个元素之前），则需要额外进行一轮将该元素移动到数组末尾的操作。计算这些额外操作的总次数加上数组长度即为答案。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def countOperationsToEmptyArray(self, nums: List[int]) -> int:
# 对 nums 的索引按对应值排序
index = sorted(range(len(nums)), key=lambda k: nums[k])
# 初始化操作次数为数组长度
total = len(index)
# 用于记录前一个元素的位置
pre = 0
# 遍历排序后的索引
for i in range(len(index)):
# 如果当前元素索引小于前一个，需要额外操作
if index[i] < pre:
total += len(index) - i
# 更新前一个元素的索引
pre = index[i]
return total
在数组操作中，按照数值排序的逻辑主要是为了确定操作的优先顺序，即我们希望优先处理数值较小的元素。这种排序方法可以帮助我们更系统地理解和模拟数组元素被逐一清除的过程。具体来说，通过排序，我们可以获得一个有序的处理顺序，这有助于我们计算出移动元素时的额外操作次数。这种方法类似于优先处理任务队列中优先级较高的任务，从而使整体操作更为高效。
在按值排序的索引列表中，如果当前元素的索引小于前一个元素的索引，这表明在原始数组中，当前元素位于前一个元素之前。因此，当我们按排序后的顺序处理数组元素时，要移动当前元素到数组末尾去清除，就必须越过前面已处理的元素，这就需要额外的操作。这种情况需要额外操作是因为我们需要保持数组的其余部分的相对顺序，使得每次移动都能有效地将一个元素移到正确位置以便清除。
表达式`len(index) - i`表示从当前元素开始到数组末尾的元素数量。在这个算法中，如果发现当前元素的索引小于前一个元素的索引，意味着为了将当前元素移动到数组末尾，我们需要执行额外的操作次数，等于从当前元素位置到数组末尾的元素总数。这是因为每移动一次，当前元素都需要越过所有这些元素，以到达数组的末端。
如果排序后的索引列表中存在连续的递减元素索引，每当遇到这种情况时，每个这样的元素都需要额外的操作来移动到数组的末尾。具体的操作次数为这个元素到数组末端的元素总数，即`len(index) - 当前元素的位置i`。这些操作会累加，因为每个元素都独立需要被移动到末尾。因此，这种连续递减的索引会导致操作次数的显著增加，每个这样的元素都按照其到数组末尾的距离计算需要额外的操作次数。