LeetCode Ts-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.

你給予一個正整數組成的陣列 nums。從 score = 0 開始，執行以下演算法：
選擇陣列中尚未被標記的最小整數，如果有多個相同最小值，選擇 index 較小的，
將所選整數的直加到 score 上，將所選元素以及他的兩個相鄰元素(如果存在)標記起來。
重複以上步驟，直到所有元素陣列都被標記為止。
回傳執行上述演算法後的 score。

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.

Solution:
我們先將元素與索引配對並排序。
// pairs = [[2, 0], [1, 1], [3, 2], [4, 3], [5, 4], [2, 5]]
// pairs.sort() = [[1, 1], [2, 0], [2, 5], [3, 2], [4, 3], [5, 4]]
每次選未標記的最小值時，就把它與相鄰元素標記並累加到 score，
最後回傳 score。

Code 1: BigO(n log n)

function findScore(nums: number[]): number {
    const pairs: number[][] = nums.map((num, idx) => [num, idx] as [number, number]); 
    pairs.sort((a, b) => a[0] - b[0] || a[1] - b[1]);     
    const marked: boolean[] = Array(nums.length).fill(false);
    let score: number = 0;

    for (const [num, i] of pairs) {
        if (!marked[i]) {
            score += num;
            if (i > 0) marked[i - 1] = true;
            marked[i] = true;
            if (i < nums.length - 1) marked[i + 1] = true;
        }
    }
    return score;
};

FlowChart:
Example 1

Input: nums = [2,1,3,4,5,2]

pairs [ [ 2, 0 ], [ 1, 1 ], [ 3, 2 ], [ 4, 3 ], [ 5, 4 ], [ 2, 5 ] ]
pairs [ [ 1, 1 ], [ 2, 0 ], [ 2, 5 ], [ 3, 2 ], [ 4, 3 ], [ 5, 4 ] ]
num 1 index 1 score 1
marked: [ true, true, true, false, false, false ]
num 2 index 5 score 3
marked: [ true, true, true, false, true, true ]
num 4 index 3 score 7
marked: [ true, true, true, true, true, true ]
return score; // 7

Example 2

Input: nums = [2,3,5,1,3,2]

pairs [ [ 2, 0 ], [ 3, 1 ], [ 5, 2 ], [ 1, 3 ], [ 3, 4 ], [ 2, 5 ] ]
pairs [ [ 1, 3 ], [ 2, 0 ], [ 2, 5 ], [ 3, 1 ], [ 3, 4 ], [ 5, 2 ] ]
num 1 index 3 score 1
marked: [ false, false, true, true, true, false ]
num 2 index 0 score 3
marked: [ true, true, true, true, true, false ]
num 2 index 5 score 5
marked: [ true, true, true, true, true, true ]
return score; // 5