Re: [閒聊] 每日leetcode
3346. Maximum Frequency of an Element After Performing Operations I
3347. Maximum Frequency of an Element After Performing Operations II
兩題差不多，放在一起講
思路:
先記錄nums中每個數字出現的次數
找出nums矩陣裡的最大值maxnum
接著從0~maxnum每個數都去找距離這個數[-k,k]以內的值在nums出現的次數
基本上類似prefixsum
從0 -> maxnum跑一次、maxnum -> 0再跑一次
最後找出0~maxnum中是哪個值在[-k,k]這個範圍內在nums出現最多次
就是答案了
golang code :
func maxFrequency(nums []int, k int, numOperations int) int {
max_num := slices.Max(nums)
count, adjacent := make([]int, max_num+1), make([]int, max_num+1)
for _, val := range nums {
count[val]++
}
adj := 0
for i := 0; i <= max_num; i++ {
if i-k-1 > -1 {
adj -= count[i-k-1]
}
adjacent[i] = adj
adj += count[i]
}
ans, adj := 0, 0
for i := max_num; i > -1; i-- {
if i+k+1 <= max_num {
adj -= count[i+k+1]
}
adjacent[i] += adj
adj += count[i]
ans = max(ans, count[i]+min(numOperations, adjacent[i]))
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.160.205 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732799638.A.13E.html
討論串 (同標題文章)
完整討論串 (本文為第 1166 之 1548 篇)：