Medium
题目描述
给定一个大小为 n 的数组 nums，由非负整数组成。你的任务是对数组进行一些（可能为零次）操作，使所有元素都变为 0。
在一次操作中，你可以选择一个子数组 [i, j]（其中 0 <= i <= j < n），并将该子数组中最小的非负整数的所有出现都设置为 0。
返回使数组中所有元素都变为 0 所需的最少操作次数。
示例 1：
输入：nums = [0,2]
输出：1
解释： 选择子数组 [1,1]（即 [2]），其中最小的非负整数是 2。将所有出现的 2 设置为 0，得到 [0,0]。 因此，所需的最少操作次数为 1。
示例 2：
输入：nums = [3,1,2,1]
输出：3
解释： 选择子数组 [1,3]（即 [1,2,1]），其中最小的非负整数是 1。将所有出现的 1 设置为 0，得到 [3,0,2,0]。 选择子数组 [2,2]（即 [2]），其中最小的非负整数是 2。将所有出现的 2 设置为 0，得到 [3,0,0,0]。 选择子数组 [0,0]（即 [3]），其中最小的非负整数是 3。将所有出现的 3 设置为 0，得到 [0,0,0,0]。 因此，所需的最少操作次数为 3。
示例 3：
输入：nums = [1,2,1,2,1,2]
输出：4
约束条件：
- 1 <= n == nums.length <= 10^5
- 0 <= nums[i] <= 10^5
提示：
- 按从小到大的顺序处理 nums 中的值（不包括 0）。
- 对于每个目标值 v，识别其最大连续段（nums[i] == v 的子数组）；每个段可以在一次操作中归零。
- 将这些段设置为零后，动态更新剩余数组并对下一个值重复。
解题思路
解题思路
这道题的核心思想是贪心策略结合排序处理。关键观察是：我们必须按照从小到大的顺序处理非零值，因为操作会将子数组中的最小值设为零。
主要思路：
排序处理：将所有非零值按升序排序，这样确保每次操作时，当前值确实是子数组中的最小值。
连续段计算：对于每个值，我们需要计算它形成了多少个连续的段。每个连续段需要一次操作来清零。关键是要考虑已经被清零的位置对连续性的影响。
动态更新：使用布尔数组标记哪些位置已被清零。当处理某个值时，只考虑尚未被清零的相同值的位置，计算它们形成的连续段数量。
优化实现：可以使用哈希表存储每个值的所有位置，然后按值的大小依次处理。
算法步骤：
- 遍历数组，记录每个非零值及其所有出现位置
- 按值的大小升序处理每个非零值
- 对于当前值，在未被清零的位置中计算连续段数量
- 将该值的所有位置标记为已清零
- 累加操作次数
这种方法确保了每次操作都是最优的，因为我们总是选择当前可处理的最小值，并且最大化每次操作的效果。
代码实现
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
map<int, vector<int>> positions;
// Record positions of each non-zero value
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
positions[nums[i]].push_back(i);
}
}
vector<bool> cleared(n, false);
int operations = 0;
// Process values in ascending order
for (auto& [value, pos] : positions) {
int segments = 0;
bool inSegment = false;
// Count contiguous segments for this value
for (int p : pos) {
if (!cleared[p]) {
if (!inSegment) {
segments++;
inSegment = true;
}
} else {
inSegment = false;
}
}
operations += segments;
// Mark all positions of this value as cleared
for (int p : pos) {
cleared[p] = true;
}
}
return operations;
}
};
class Solution:
def minOperations(self, nums: List[int]) -> int:
from collections import defaultdict
n = len(nums)
positions = defaultdict(list)
# Record positions of each non-zero value
for i, num in enumerate(nums):
if num != 0:
positions[num].append(i)
cleared = [False] * n
operations = 0
# Process values in ascending order
for value in sorted(positions.keys()):
pos_list = positions[value]
segments = 0
in_segment = False
# Count contiguous segments for this value
for p in pos_list:
if not cleared[p]:
if not in_segment:
segments += 1
in_segment = True
else:
in_segment = False
operations += segments
# Mark all positions of this value as cleared
for p in pos_list:
cleared[p] = True
return operations
public class Solution {
public int MinOperations(int[] nums) {
int n = nums.Length;
var positions = new Dictionary<int, List<int>>();
// Record positions of each non-zero value
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
if (!positions.ContainsKey(nums[i])) {
positions[nums[i]] = new List<int>();
}
positions[nums[i]].Add(i);
}
}
bool[] cleared = new bool[n];
int operations = 0;
// Process values in ascending order
var sortedKeys = positions.Keys.OrderBy(x => x);
foreach (int value in sortedKeys) {
var posList = positions[value];
int segments = 0;
bool inSegment = false;
// Count contiguous segments for this value
foreach (int p in posList) {
if (!cleared[p]) {
if (!inSegment) {
segments++;
inSegment = true;
}
} else {
inSegment = false;
}
}
operations += segments;
// Mark all positions of this value as cleared
foreach (int p in posList) {
cleared[p] = true;
}
}
return operations;
}
}
var minOperations = function(nums) {
const n = nums.length;
const positions = new Map();
// Record positions of each non-zero value
for (let i = 0; i < n; i++) {
if (nums[i] !== 0) {
if (!positions.has(nums[i])) {
positions.set(nums[i], []);
}
positions.get(nums[i]).push(i);
}
}
const cleared = new Array(n).fill(false);
let operations = 0;
// Process values in ascending order
const sortedValues = Array.from(positions.keys()).sort((a, b) => a - b);
for (const value of sortedValues) {
const posList = positions.get(value);
let segments = 0;
let inSegment = false;
// Count contiguous segments for this value
for (const p of posList) {
if (!cleared[p]) {
if (!inSegment) {
segments++;
inSegment = true;
}
} else {
inSegment = false;
}
}
operations += segments;
// Mark all positions of this value as cleared
for (const p of posList) {
cleared[p] = true;
}
}
return operations;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n log n)，其中 n 是数组长度。主要开销来自对值的排序和遍历所有位置 |
| 空间复杂度 | O(n)，用于存储位置信息和标记数组 |