py3 C++ Line sweep解Leetcode 3346 Maximum Frequency of an Element After ...

py3 cpp Line sweep解Leetcode 3346  Maximum Frequency of an Element After Performing Operations I

使用 line sweep不用排序，可得線性解

[Py3解請進]

-------

Use line sweep without sorting to get a linear solution

[codes on Leetcode]https://leetcode.com/problems/maximum-frequency-of-an-element-after-performing-operations-i/solutions/7289403/line-sweep-vs-prefix-sum-sliding-window-beats-99-51/

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        M=max(nums)+2
        freq, sweep=[0]*M, [0]*M
        mm=M
        for x in nums:
            freq[x]+=1
            s, t=max(1, x-k), min(M-1, x+k+1)
            sweep[s]+=1
            sweep[t]-=1
            mm=min(mm, s)
        ans, cnt=0, 0
        for x in range(mm, M):
            cnt+=sweep[x]
            ans=max(ans, freq[x]+min(numOperations, cnt-freq[x]))
        return ans