[LeetCode] 2593. Find Score of an Array After Marking All Elements

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.

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 <= 105
1 <= nums[i] <= 106

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

给你一个数组 nums ，它包含若干正整数。

一开始分数 score = 0 ，请你按照下面算法求出最后分数：

• 从数组中选择最小且没有被标记的整数。如果有相等元素，选择下标最小的一个。
  将选中的整数加到 score 中。
• 标记 被选中元素，如果有相邻元素，则同时标记 与它相邻的两个元素 。
• 重复此过程直到数组中所有元素都被标记。

请你返回执行上述算法后最后的分数。

思路

思路就是模拟。这里我创建了一个二维数组，记录了原数组里的每个元素及其下标。然后我对这个二位数组排序，元素小的在前，元素相同的时候，下标小的在前。这样当我开始扫描这个二维数组的时候，首先遇到的是最小的元素而且他的下标也是最小的。同时我还需要一个和 input 数组等长的 Boolean 数组，记录每个下标是否被访问过。

开始遍历二维数组，如果当前位置没有被访问过，则把当前位置这个数字累加到 res 上，然后把他的左右邻居也标记成访问过。

复杂度

时间O(nlogn)
空间O(2n) ~ O(n)

代码

Java实现

class Solution {
    public long findScore(int[] nums) {
        int n = nums.length;
        int[][] numbers = new int[n][2];
        for (int i = 0; i < n; i++) {
            numbers[i][0] = nums[i];
            numbers[i][1] = i;
        }
        Arrays.sort(numbers, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        boolean[] visited = new boolean[n];
        long res = 0;
        for (int[] number : numbers) {
            int num = number[0];
            int index = number[1];
            if (visited[index] == false) {
                visited[index] = true;
                res += num;
                // left
                if (index - 1 >= 0) {
                    visited[index - 1] = true;
                }
                // right
                if (index + 1 < n) {
                    visited[index + 1] = true;
                }
            }
        }
        return res;
    }
}