2025-06-01：執行操作后元素的最高頻率Ⅰ。用go語言，給定一個整數數組 nums 和兩個整數 k 以及 numOperations。

你需要對數組 nums 進行恰好 numOperations 次操作。每次操作的步驟如下：

• ? 選擇一個之前沒有選擇過的下標 i。

• ? 將 nums[i] 增加一個在區間 [-k, k] 內的任意整數。

完成所有操作后，計算數組中出現次數最多的元素出現的頻率，并返回這個最大頻率。

1 <= nums.length <= 100000。

1 <= nums[i] <= 100000。

0 <= k <= 100000。

0 <= numOperations <= nums.length。

輸入：nums = [5,11,20,20], k = 5, numOperations = 1。

輸出：2。

解釋：

通過以下操作得到最高頻率 2 ：

將 nums[1] 增加 0 。

題目來自力扣3346。

關鍵觀察：

1. 1.排序：首先將數組排序，這樣我們可以更容易地計算某個區間內的元素是否可以通過操作調整到同一個值。

2. 2.滑動窗口：使用滑動窗口的思想來找到最長的子數組，其中所有元素可以通過最多numOperations次操作調整到同一個值。

3. 3.操作分配：對于窗口內的元素，我們需要計算將它們調整到某個目標值（通常是窗口的右端或左端）所需的總操作次數，并確保這個總操作次數不超過numOperations的限制。

1. 1.排序數組：將nums排序，以便后續的滑動窗口處理。

2. 2.初始化指針和變量：使用left、right指針表示滑動窗口的左右邊界，cnt用于統計當前窗口內相同元素的連續出現次數。

3. 3.滑動窗口擴展：

• ? 對于每個元素nums[i]，嘗試擴展窗口的右邊界right，使得窗口內的所有元素可以通過最多numOperations次操作調整到nums[i]。

• ? 計算將窗口內所有元素調整到nums[i]所需的總操作次數。這可以通過前綴和或累加的方式計算。

• ? 如果總操作次數超過numOperations，則移動左邊界left以減少操作次數。

• ? 更新最大頻率ans。

4.處理連續相同元素：如果當前元素與下一個元素相同，直接跳過，因為它們已經可以貢獻頻率。

5.考慮操作限制：由于最多只能進行numOperations次操作，因此最大頻率不能超過numOperations + 1（即最多調整numOperations個元素到某個值，加上該值本身可能已經存在）。

時間復雜度和空間復雜度

• ?時間復雜度：

• • ? 排序：O(n log n)，其中n是nums的長度。

  • ? 滑動窗口：每個元素最多被訪問兩次（left和right指針各一次），因此是O(n)。

  • ? 總時間復雜度：O(n log n)（排序主導）。

• ?空間復雜度：

• • ? 排序可能需要O(log n)的棧空間（取決于排序算法）。

  • ? 其他變量是常數空間。

  • ? 總空間復雜度：O(log n)。

package main import (     "fmt"     "slices" ) func maxFrequency(nums []int, k, numOperations int) (ans int) {     slices.Sort(nums)     n := len(nums)     var cnt, left, right, left2 int     for i, x := range nums {         for nums[left2] < x-k*2 {             left2++         }         ans = max(ans, min(i-left2+1, numOperations))         cnt++         // 循環直到連續相同段的末尾，這樣可以統計出 x 的出現次數         if i < n-1 && x == nums[i+1] {             continue         }         for nums[left] < x-k {             left++         }         for right < n && nums[right] <= x+k {             right++         }         ans = max(ans, min(right-left, cnt+numOperations))         cnt = 0     }     return } func main() {     nums := []int{5,11,20,20}     k := 5     numOperations := 1     result := maxFrequency(nums,k,numOperations)     fmt.Println(result) }

Python完整代碼如下：

# -*-coding:utf-8-*- from bisect import bisect_left, bisect_right defmaxFrequency(nums, k, numOperations):     nums.sort()     n = len(nums)     ans = 0     cnt = 0     left = 0     right = 0     left2 = 0          for i, x inenumerate(nums):         while left2 < n and nums[left2] < x - 2 * k:             left2 += 1         ans = max(ans, min(i - left2 + 1, numOperations))                  cnt += 1         if i < n - 1and x == nums[i + 1]:             continue                  while left < n and nums[left] < x - k:             left += 1         while right < n and nums[right] <= x + k:             right += 1                  ans = max(ans, min(right - left, cnt + numOperations))         cnt = 0              return ans if __name__ == "__main__":     nums = [5, 11, 20, 20]     k = 5     numOperations = 1     result = maxFrequency(nums, k, numOperations)     print(result)

我們相信 Go 語言和算法為普通開發者提供了強有力的“面試利器”，并致力于分享全面的編程知識。在這里，您可以找到最新的 Go 語言教程、算法解析、提升面試競爭力的秘籍以及行業動態。 歡迎關注“福大大架構師每日一題”，讓 Go 語言和算法助力您的職業發展