LeetCode 筆記 - 1838. Frequency of the Most Frequent Element

Posted on

題目在此 1838. Frequency of the Most Frequent Element

給定一個數列 nums 跟一個整數 k，我們可以對 nums 中的任意元素加上 1 最多 k 次，請問最多可以有幾個相同元素？

解題思維

名詞解說：

跟頻率相關的題目，通常可以用排序來處理，這題也不例外。image 106

排序之後，我們用兩個指標 left 跟 right 來表示一個視窗，如果我們可以用 k 來把這個視窗填滿，也就是說除了 nums[right] 以外，nums[left], nums[left + 1], nums[left + ...] 都要跟 nums[right] 相等。
如此一來，我們就可以把 right - left + 1當作是目前視窗的最大頻率。

而視窗如果可以使用 k 來填滿的總和上限就是 nums[right] * (right - left + 1)，而這個總合不應該超過 sum(nums[left: right + 1]) + k，如果超過的話，就代表我們需要將 left 往右移動，直到視窗可以使用 k 來填滿。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:

        nums.sort()
        
        result = 1
        current_sum = k
        left = 0

        for right in range(len(nums)):
            current_sum += nums[right]
            while nums[right] * (temp := right - left + 1) > current_sum:
                current_sum -= nums[left]
                left += 1

            result = max(result, temp)

        return result
image 106

也許你也會想看看