2024-05-09|閱讀時間 ‧ 約 26 分鐘

快樂崇拜 小朋友的快樂值 Leetcode #3075


題目敘述

輸入給定一個整數陣列,分別代表每小朋友的快樂值

要求我們選擇其中最快樂的k位小朋友,累加這群小朋友的快樂值


有一個特殊的規則,第一位選中的小朋友快樂值不變。

接著,第二位選中的小朋友快樂值-1

再接著,第三位選中的小朋友快樂值-2

快樂值扣到只剩下0就不再往下扣

...其餘依此類推


輸出時整數返回答案


原本的英文題目敘述


測試範例

Example 1:

Input: happiness = [1,2,3], k = 2
Output: 4
Explanation: We can pick 2 children in the following way:
- Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
- Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0.
The sum of the happiness values of the selected children is 3 + 1 = 4.

Example 2:

Input: happiness = [1,1,1,1], k = 2
Output: 1
Explanation: We can pick 2 children in the following way:
- Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
- Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
The sum of the happiness values of the selected children is 1 + 0 = 1.

Example 3:

Input: happiness = [2,3,4,5], k = 1
Output: 5
Explanation: We can pick 1 child in the following way:
- Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
The sum of the happiness values of the selected children is 5.

約束條件

Constraints:

  • 1 <= n == happiness.length <= 2 * 10^5

小朋友的總數介於1~二十萬 之間。

  • 1 <= happiness[i] <= 10^8

每味小朋友的快樂值介於1~一億 之間。

  • 1 <= k <= n

k值介於 1 ~ n 之間。


演算法 排序 或 最大堆MaxHeap

題目很明顯是要挑前k個最大的元素

這個需求可以透過排序或者建造最大堆MaxHeap來滿足

兩種解法都可以,最後複雜度也是同樣O( n log n )等級的。


有一個實作上的細節請留意,題目有額外特殊的規則,每挑一人,快樂值會遞減,一直扣到剩下零為止


程式碼 排序 或 最大堆MaxHeap

class Solution:
def maximumHappinessSum(self, happiness: List[int], k: int) -> int:

happiness.sort( reverse = True )

summation = 0

for i in range(k):

summation += max(happiness[i] - i, 0)

return summation

程式碼 最大堆MaxHeap

class Solution:
def maximumHappinessSum(self, happiness: List[int], k: int) -> int:

heapq._heapify_max(happiness)

summation = 0

for i in range(k):
cur_largest = heapq._heappop_max(happiness)
summation += max(cur_largest - i, 0)

return summation

複雜度分析

時間複雜度: O(n log n)

n個數值進行排序,所需時間為O( n log n)。


空間複雜度: O(1)

in-place排序,in-place建造最大堆,其他用到的都是固定尺寸的O(1)臨時變數。


關鍵知識點

挑前k個最大的元素

這個需求可以透過排序或者建造最大堆MaxHeap來滿足


Reference

[1] Maximize Happiness of Selected Children - LeetCode

分享至
成為作者繼續創作的動力吧!
© 2024 vocus All rights reserved.