将数组清空
难度:
标签:
题目描述
You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty:
- If the first element has the smallest value, remove it
- Otherwise, put the first element at the end of the array.
Return an integer denoting the number of operations it takes to make nums empty.
Example 1:
Input: nums = [3,4,-1] Output: 5
| Operation | Array |
|---|---|
| 1 | [4, -1, 3] |
| 2 | [-1, 3, 4] |
| 3 | [3, 4] |
| 4 | [4] |
| 5 | [] |
Example 2:
Input: nums = [1,2,4,3] Output: 5
| Operation | Array |
|---|---|
| 1 | [2, 4, 3] |
| 2 | [4, 3] |
| 3 | [3, 4] |
| 4 | [4] |
| 5 | [] |
Example 3:
Input: nums = [1,2,3] Output: 3
| Operation | Array |
|---|---|
| 1 | [2, 3] |
| 2 | [3] |
| 3 | [] |
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109- All values in
numsare distinct.
代码结果
运行时间: 135 ms, 内存: 27.7 MB
/* 思路: 通过Java Stream API，我们可以更简洁地实现这个操作。虽然Stream API不能直接改变集合，但我们可以使用流来获取最小值。然后，通过移除和添加元素来模拟操作。*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int removeElements(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) list.add(num);
int operations = 0;
while (!list.isEmpty()) {
int min = list.stream().min(Integer::compare).get(); // 获取最小值
if (list.get(0) == min) {
list.remove(0); // 删除最小值
} else {
list.add(list.remove(0)); // 移动第一个元素到末尾
}
operations++;
}
return operations;
}
}
解释
方法:
题解利用了排序和索引来优化操作。首先，通过对数组元素的索引进行排序（基于它们的值），我们获得一个有序的索引列表，该列表直接指向数组中从最小值到最大值的元素。接下来，遍历这个有序索引列表，计算清空数组所需的总操作次数。对于每个元素，如果其索引小于前一个元素的索引（说明在原数组中，这个元素在前一个元素之前），则需要额外进行一轮将该元素移动到数组末尾的操作。计算这些额外操作的总次数加上数组长度即为答案。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中，你是如何确定将数组索引按照对应数值排序后的逻辑与原题目操作的对应关系的？
▷🦆
题解中提到，如果当前元素的索引小于前一个元素的索引就需要额外操作，能否详细解释为什么这样的条件会导致需要额外的操作？
▷🦆
在计算额外操作次数时，为什么使用了`len(index) - i`这个表达式？这个表达式具体代表什么意义？
▷🦆
排序后的索引列表中，如果有连续几个元素的索引是递减的，这种情况下的操作次数是怎样累计的？
▷