2593. Find Score of an Array After Marking All Elements

Problem

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.

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

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⁵
• 1 <= nums[i] <= 10⁶

Test Cases

1
2

class Solution:
    def findScore(self, nums: List[int]) -> int:

1
2
3
4
5
6
7
8
9
10
11
12
13

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([2,1,3,4,5,2], 7),
    ([2,3,5,1,3,2], 5),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.findScore(nums) == expected

Thoughts

直接对 nums 排序。但还需要保留位置信息，可以创建一个下标数组，对其按 nums 值排序。另外用一个数组记录 nums 中哪些值被标记了。

时间 O(n log n)，空间 O(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def findScore(self, nums: list[int]) -> int:
        n = len(nums)
        indices = list(range(n))
        indices.sort(key=lambda i: nums[i])
        marks = [False] * n
        score = 0
        for i in indices:
            if marks[i]: continue
            score += nums[i]
            marks[i] = True
            if i > 0: marks[i - 1] = True
            if i < n - 1: marks[i + 1] = True

        return score

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章