Skip to content

Latest commit

 

History

History
117 lines (70 loc) · 3.47 KB

2593.find-score-of-an-array-after-marking-all-elements.md

File metadata and controls

117 lines (70 loc) · 3.47 KB

题目地址(2593. 标记所有元素后数组的分数)

https://leetcode.cn/problems/find-score-of-an-array-after-marking-all-elements/

题目描述

给你一个数组 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 <= 105
1 <= nums[i] <= 106

前置知识

  • 哈希表

公司

  • 暂无

思路

将 nums 排序,并从小到大取,比如当前取的是索引为 i 的。那么取完要更新:

  1. 索引 i 为已访问
  2. 索引 i-1 为已访问(如果存在)
  3. 索引 i+1 为已访问(如果存在)

更新完访问状态后更新一下得分,即将分数加上 nums[i] 即可。

当然,我们在取 i 之前要先判断是否已访问,如果未访问才执行上面的操作。

关键点

  • 哈希表记录每个元素的访问状态

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def findScore(self, nums: List[int]) -> int:
        ans = 0
        vis = [False] * (len(nums) + 2)  # 保证下标不越界
        for i, x in sorted(enumerate(nums, 1), key=lambda p: p[1]):
            if not vis[i]:
                vis[i - 1] = True
                vis[i + 1] = True  # 标记相邻的两个元素
                ans += x
        return ans

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(nlogn)$
  • 空间复杂度:不确定,取决于内置的排序算法

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。