2025-06-01：执行操作后元素的最高频率Ⅰ。用go语言，给定一个整数数组 nums 和两个整数 k 以及 numOpera

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 语言和算法助力您的职业发展