LeetCode 题解工作台
标记所有元素后数组的分数
给你一个数组 nums ，它包含若干正整数。 一开始分数 score = 0 ，请你按照下面算法求出最后分数： 从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。 将选中的整数加到 score 中。 标记 被选中元素 ，如果有相邻元素，则同时标记 与它相邻的两个元素 。 重复此…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个优先队列维护数组中未被标记的元素，队列中每一项为一个二元组 $(x, i)$，其中 和 分别表示数组中的元素值和下标，用一个数组 记录数组中的元素是否被标记。 每次从队列中取出最小的元素 $(x, i)$，我们将 加入答案，然后标记 位置的元素，以及 位置的左右相邻元素，即 $i - 1$ 和 $i + 1$ 位置的元素。接下来判断堆顶元素是否被标记，如果被标记则弹出堆顶元素…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个数组 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 <= 1051 <= nums[i] <= 106
解题思路
方法一：优先队列（小根堆）
我们用一个优先队列维护数组中未被标记的元素，队列中每一项为一个二元组 ，其中 和 分别表示数组中的元素值和下标，用一个数组 记录数组中的元素是否被标记。
每次从队列中取出最小的元素 ，我们将 加入答案，然后标记 位置的元素，以及 位置的左右相邻元素，即 和 位置的元素。接下来判断堆顶元素是否被标记，如果被标记则弹出堆顶元素，直到堆顶元素未被标记，或者堆为空。
最后返回答案即可。
时间复杂度 ，空间复杂度 。其中 为数组的长度。
class Solution:
def findScore(self, nums: List[int]) -> int:
n = len(nums)
vis = [False] * n
q = [(x, i) for i, x in enumerate(nums)]
heapify(q)
ans = 0
while q:
x, i = heappop(q)
ans += x
vis[i] = True
for j in (i - 1, i + 1):
if 0 <= j < n:
vis[j] = True
while q and vis[q[0][1]]:
heappop(q)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate can efficiently simulate the marking process and handle adjacent element marking without redundancies.
- question_mark
The candidate demonstrates a clear understanding of how hash lookups optimize the process of marking elements.
- question_mark
The candidate can explain how the array scanning mechanism works within the algorithm.
常见陷阱
外企场景- error
Not correctly managing the marking process for adjacent elements, leading to missed or incorrectly marked elements.
- error
Using inefficient data structures or algorithms that cause the solution to exceed the time complexity limits.
- error
Failing to correctly simulate the marking process, causing incorrect score calculations.
进阶变体
外企场景- arrow_right_alt
Consider optimizing the algorithm to handle larger arrays with even stricter time limits.
- arrow_right_alt
Change the rule for marking adjacent elements, such as marking only one neighbor instead of two.
- arrow_right_alt
Alter the marking process to skip certain elements based on additional conditions, like element frequency.