2593. 标记所有元素后数组的分数
2593. 标记所有元素后数组的分数
🟠 🔖 数组 哈希表 排序 模拟 堆（优先队列） 🔗 力扣 LeetCode
题目
You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
- Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
- Add the value of the chosen integer to
score. - Mark the chosen element and its two adjacent elements if they exist.
- Repeat until all the array elements are marked.
Return the score you get after applying the above algorithm.
Example 1:
Input: nums =
[2,1,3,4,5,2]Output: 7
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements:
[_2_ ,_1_ ,_3_ ,4,5,2].- 2 is the smallest unmarked element, so we mark it and its left adjacent element:
[_2_ ,_1_ ,_3_ ,4,_5_ ,_2_].- 4 is the only remaining unmarked element, so we mark it:
[_2_ ,_1_ ,_3_ ,_4_ ,_5_ ,_2_].Our score is 1 + 2 + 4 = 7.
Example 2:
Input: nums =
[2,3,5,1,3,2]Output: 5
Explanation: We mark the elements as follows:
- 1 is the smallest unmarked element, so we mark it and its two adjacent elements:
[2,3,_5_ ,_1_ ,_3_ ,2].- 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element:
[_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,2].- 2 is the only remaining unmarked element, so we mark it:
[_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,_2_].Our score is 1 + 2 + 2 = 5.
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
题目大意
给你一个数组 nums ，它包含若干正整数。
一开始分数 score = 0 ，请你按照下面算法求出最后分数：
- 从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
- 将选中的整数加到
score中。 - 标记 被选中元素 ，如果有相邻元素，则同时标记 与它相邻的两个元素 。
- 重复此过程直到数组中所有元素都被标记。
请你返回执行上述算法后最后的分数。
示例 1：
输入： nums =
[2,1,3,4,5,2]输出： 7
解释： 我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：
[_2_ ,_1_ ,_3_ ,4,5,2]。- 2 是最小未标记元素，所以标记它和左边相邻元素：
[_2_ ,_1_ ,_3_ ,4,_5_ ,_2_]。- 4 是仅剩唯一未标记的元素，所以我们标记它：
[_2_ ,_1_ ,_3_ ,_4_ ,_5_ ,_2_]。总得分为 1 + 2 + 4 = 7 。
示例 2：
输入： nums = [2,3,5,1,3,2]
输出： 5
解释： 我们按照如下步骤标记元素：
- 1 是最小未标记元素，所以标记它和相邻两个元素：
[2,3,_5_ ,_1_ ,_3_ ,2]。- 2 是最小未标记元素，由于有两个 2 ，我们选择最左边的一个 2 ，也就是下标为 0 处的 2 ，以及它右边相邻的元素：
[_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,2]。- 2 是仅剩唯一未标记的元素，所以我们标记它：
[_2_ ,_3_ ,_5_ ,_1_ ,_3_ ,_2_]。总得分为 1 + 2 + 2 = 5 。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
解题思路
- 使用排序优化最小值查找
为了快速找到未标记的最小值，先将 nums 中的每个元素与其下标存入数组 arr，并按元素值升序排序。
这样，遍历 arr 时，最小值总是优先处理，避免每次查找时都遍历整个数组。
- 使用集合记录标记状态
使用一个集合 marked 来记录已被标记的元素下标。
- 遍历
arr
对每个元素，先判断其是否未被标记（!marked.has(idx)），若未标记则：
- 将该值累加到分数。
- 标记当前元素的下标以及其左右相邻的下标。
- 返回最终分数
复杂度分析
- 时间复杂度：
O(n log n)- 创建并排序数组
arr：O(n log n) - 遍历排序后的数组：
O(n) - 总体复杂度：
O(n log n)
- 创建并排序数组
- 空间复杂度：
O(n)- 排序后的数组
arr占用O(n) - 用于记录标记状态的集合
marked占用O(n) - 总体空间复杂度：
O(n)
- 排序后的数组
代码
/**
* @param {number[]} nums
* @return {number}
*/
var findScore = function (nums) {
// 创建一个数组，包含每个元素及其原下标，并按值排序
const arr = nums.map((num, idx) => [num, idx]).sort((a, b) => a[0] - b[0]);
// 用于记录已标记的下标
let marked = new Set();
let score = 0;
for (let [val, idx] of arr) {
// 如果当前下标未被标记
if (!marked.has(idx)) {
// 累加分数
score += val;
// 标记当前元素
marked.add(idx);
// 标记相邻元素
if (idx > 0) marked.add(idx - 1);
if (idx < nums.length - 1) marked.add(idx + 1);
}
}
return score;
};
相关题目
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
|---|---|---|---|---|---|
| 1387 | 将整数按权重排序 | 记忆化搜索 动态规划 排序 | 🟠 | 🀄️ 🔗 |