LeetCode Ts-2592. Maximize Greatness of an Array

    AllenLi
    CodingLeetCode Js-Two Pointers

    You are given a 0-indexed integer array nums. You are allowed to permute nums into a new array perm of your choosing.
    We define the greatness of nums be the number of indices 0 <= i < nums.length for which perm[i] > nums[i].
    Return the maximum possible greatness you can achieve after permuting nums.

    妳有一個從 0 索引開始的整數陣列 nums。
你可以重新排列（permute） 這個陣列，得到一個新的陣列 perm（由你自由決定順序）。
我們定義 nums 的「偉大值（greatness）」為：
滿足條件 perm[i] > nums[i] 的索引 i 的數量。
請你返回在所有可能排列中，所能達到的 最大偉大值。

    Example 1:

    Input: nums = [1,3,5,2,1,3,1]
Output: 4
Explanation: One of the optimal rearrangements is perm = [2,5,1,3,3,1,1].
At indices = 0, 1, 3, and 4, perm[i] > nums[i]. Hence, we return 4.

    Example 2:

    Input: nums = [1,2,3,4]
Output: 3
Explanation: We can prove the optimal perm is [2,3,4,1].
At indices = 0, 1, and 2, perm[i] > nums[i]. Hence, we return 3.

    Solution:
    先將陣列排序好，然後用 i, j 雙指針來進行比大小，
    當右指針比左指針大，代表找到 greatness 數值 count + 1，
    同時兩個指針分別往前移動，遍歷完迴圈後回完 count。
    這題可以模擬一下過程：

    nums: [1, 1, 1, 2, 3, 3, 5]
       ↑
perm: [1, 1, 1, 2, 3, 3, 5]
       ↑
比較：1 vs 1 → X  

nums: [1, 1, 1, 2, 3, 3, 5]
       ↑
perm: [1, 1, 1, 2, 3, 3, 5]
          ↑
比較：1 vs 1 → X  

nums: [1, 1, 1, 2, 3, 3, 5]
       ↑
perm: [1, 1, 1, 2, 3, 3, 5]
             ↑
比較：1 vs 1 → X  

nums: [1, 1, 1, 2, 3, 3, 5]
       ↑
perm: [1, 1, 1, 2, 3, 3, 5]
                ↑
比較：1 vs 2 → ok
→ count = 1, i++, j++

    Code 1: BigO(n log n)

    function maximizeGreatness(nums: number[]): number {
    const sortedNums: number[] = nums.sort((a, b) => a - b);
    let i: number = 0;
    let count: number = 0;
    for (let j = 0; j < nums.length; j++) {
        if (sortedNums[i] < sortedNums[j]) {
            i++
            count++;
        }
    }
    return count;
};

    FlowChart:
    Example 1

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

sortedNums [
  1, 1, 1, 2,
  3, 3, 5
]
j 0 i 0 count 0
j 1 i 0 count 0
j 2 i 0 count 0
j 3 i 1 count 1
j 4 i 2 count 2
j 5 i 3 count 3
j 6 i 4 count 4
return count; // 4

    Example 2

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

sortedNums [ 1, 2, 3, 4 ]
j 0 i 0 count 0
j 1 i 1 count 1
j 2 i 2 count 2
j 3 i 3 count 3
count 3

    Related Posts