标记所有元素后数组的分数

难度: Medium

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

Submission

运行时间: 96 ms

内存: 28.1 MB

class Solution:
    def findScore(self, nums: List[int]) -> int:
        t=[(num,i) for i,num in enumerate(nums)]
        t.sort()
        seen=set()
        res=0
        n=len(nums)
        for num,i in t:
            if i in seen:
                continue
            res+=num
            for x in [i,i+1,i-1]:
                if 0<=x<n:
                    seen.add(x)
        return res

Explain

题解采用的是贪心算法结合排序的策略。首先，创建一个由元组组成的列表，元组包含元素值和其在原始数组中的索引，然后对这个列表按元素值进行排序。排序后，从最小值开始处理每个元素，检查它是否已被标记（即是否已处理过）。如果未被标记，则将其值加到最终分数中，并标记这个元素及其相邻的元素以避免将来被选择。这个过程一直持续到所有元素都被处理过。通过这种方式，确保了每次都选取当前未标记元素中的最小值，同时考虑到了元素的相邻关系。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def findScore(self, nums: List[int]) -> int:
        # 创建一个列表，包含每个元素及其索引的元组
        t = [(num, i) for i, num in enumerate(nums)]
        # 根据元素值对元组列表进行排序
        t.sort()
        # 初始化标记集合和结果变量
        seen = set()
        res = 0
        n = len(nums)
        # 遍历排序后的元组列表
        for num, i in t:
            # 检查当前索引的元素是否已被标记
            if i in seen:
                continue
            # 将未标记元素的值加到结果中
            res += num
            # 标记当前元素及其相邻元素
            for x in [i, i+1, i-1]:
                if 0 <= x < n:
                    seen.add(x)
        # 返回最终计算的分数
        return res

Explore

如果直接遍历数组来寻找最小的未标记元素，每次寻找都需要遍历整个数组以确保找到当前未标记的最小元素，这将导致高时间复杂度。在最坏情况下，每次寻找都需要O(n)的时间，并且这需要重复进行n次，因此总的时间复杂度将达到O(n^2)。相比之下，通过一次排序（时间复杂度为O(n log n)）后，可以保证遍历排序后的列表时按顺序访问未标记的最小元素，这样整个算法的时间复杂度主要由排序决定，为O(n log n)，比直接遍历的方式更高效。

在创建元组列表并对其进行排序时，排序首先基于元素的值，若元素值相同，则默认按照元素原来在数组中的索引进行升序排序。因此，排序后的列表会自然地将相同值的元素按照其在原数组中的索引顺序排列。这样，算法在遍历排序后的列表时，对于相同的最小值会首先遇到下标最小的那个，从而确保了选择下标最小的元素。

排序过程中的时间复杂度通常是O(n log n)，这是基于使用的排序算法（如快速排序、归并排序等）决定的。这一复杂度比直接遍历数组的复杂度O(n^2)要低，使得整个算法的效率更高。虽然排序本身有一定的计算成本，但由于其一次性的计算开销与多次遍历数组相比更为高效，因此整体上，使用排序的方法可以显著提高算法处理大数据集时的效率。