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
class Solution:
def findScore(self, nums: List[int]) -> int:solution_test.py下载完整源码
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
solution.py下载完整源码
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
评论需要 JavaScript。