湖南网站设计外包哪家好,江苏省建设局官方网站查询,wordpress 元素用处,html网页设计思路题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你可以对数组执行 至多 k 次操作#xff1a;
从数组中选择一个下标 i #xff0c;将 nums[i] 增加 或者 减少 1 。最终数组的频率分数定义为数组中众数的 频率 。请你返回你可以得到的 最大 频率分数。
众数…题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你可以对数组执行 至多 k 次操作
从数组中选择一个下标 i 将 nums[i] 增加 或者 减少 1 。最终数组的频率分数定义为数组中众数的 频率 。请你返回你可以得到的 最大 频率分数。
众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。
示例 1
输入nums [1,2,6,4], k 3
输出3
解释我们可以对数组执行以下操作
- 选择 i 0 将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
- 选择 i 3 将 nums[3] 减少 1 得到数组 [2,2,6,3] 。
- 选择 i 3 将 nums[3] 减少 1 得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数出现了 3 次所以频率分数为 3 。
3 是所有可行方案里的最大频率分数。示例 2
输入nums [1,4,4,2,4], k 0
输出3
解释我们无法执行任何操作所以得到的频率分数是原数组中众数的频率 3 。提示
1 nums.length 1051 nums[i] 1090 k 1014
解题思路
先看一下滑动窗口的代码 class Solution:def maxFrequencyScore(self, nums: List[int], k: int) - int:nums.sort() # 排序数组max_freq 1 # 至少有一个数的频率l 0 # 窗口的左边界total 0 # 窗口内所有数变为窗口内最大数所需的总操作次数# r为窗口的右边界for r in range(len(nums)):# 将nums[r]加入窗口total nums[r]# 如果窗口内所有数变为nums[r]所需的操作次数超过k# 则移动左边界直到操作次数不超过kwhile nums[r] * (r - l 1) total k:total - nums[l]l 1# 更新最大频率max_freq max(max_freq, r - l 1) 每次以nums[right]作为变化的基准数不是最优策略可以优化为二分查找中位数 假定所有的 nums[i]均位于数轴上的 nums[i]的位置题目要求我们在数轴上找出一个点 t使得所有 nums[i]到 t 的距离之和最小。首先容易证明 t 不可能位于最小的nums[i]的左侧也不可能位于最大的 nums[i]的右侧否则我们「至少」能够将目标点调整为 最小的 nums[i]或 最大的 nums[i] 来得到更小的距离总和。 t 取中位数时距离之和最小。可以通过「反证法」证明略 total用累加的方式不是最优的方案数据量大时会超时可以优化为前缀和 class Solution:def maxFrequencyScore(self, nums: List[int], k: int) - int:nums.sort()left 0res 0n len(nums)# 计算前缀和prefix_sum [0]for num in nums:prefix_sum.append(prefix_sum[-1] num)def calculateCost(mid, left, right):cost_left nums[mid] * (mid - left) - (prefix_sum[mid] - prefix_sum[left])cost_right (prefix_sum[right 1] - prefix_sum[mid 1]) - nums[mid] * (right - mid)return cost_left cost_rightfor right in range(n):mid (left right) // 2# 当前窗口内将所有元素变为 nums[mid] 需要的操作次数while calculateCost(mid, left, right) k:# 如果操作次数超过 k则移动窗口左边界left 1mid (left right) // 2# 更新最大频率res max(res, right - left 1)return res 中位数贪心 右边数字为难度分 先刷462再刷2448 462. 最小操作次数使数组元素相等 II2033. 获取单值网格的最小操作数 16722448. 使数组相等的最小开销 2005
class Solution:def minCost(self, nums: List[int], cost: List[int]) - int:a sorted(zip(nums, cost))#cost可以理解为cost个nums[i]这样问题就转化为了中心数贪心问题s, mid 0, (sum(cost) 1) // 2for x, c in a:s cif s mid:return sum(abs(y - x) * c for y, c in a) # 把所有数变成 x
2607. 使子数组元素和相等 20711703. 得到连续 K 个 1 的最少相邻交换次数 2467
