class Solution {
public:
long long minOperationsToMakeMedianK(vector<int>& nums, int k) {
}
};
3107. 使数组中位数等于 K 的最少操作数
给你一个整数数组 nums 和一个 非负 整数 k 。
一次操作中，你可以选择任一下标 i ，然后将 nums[i] 加 1 或者减 1 。
请你返回将 nums 中位数 变为 k 所需要的 最少 操作次数。
一个数组的 中位数 指的是数组按 非递减 顺序排序后最中间的元素。如果数组长度为偶数，我们选择中间两个数的较大值为中位数。
示例 1：
输入：nums = [2,5,6,8,5], k = 4
输出：2
解释：我们将 nums[1] 和 nums[4] 减 1 得到 [2, 4, 6, 8, 4] 。现在数组的中位数等于 k 。所以答案为 2 。
示例 2：
输入：nums = [2,5,6,8,5], k = 7
输出：3
解释：我们将 nums[1] 增加 1 两次，并且将 nums[2] 增加 1 一次，得到 [2, 7, 7, 8, 5] 。结果数组的中位数等于 k 。所以答案为 3 。
示例 3：
输入：nums = [1,2,3,4,5,6], k = 4
输出：0
解释：数组中位数已经等于 k 了，所以不需要进行任何操作。
提示：
1 <= nums.length <= 2 * 1051 <= nums[i] <= 1091 <= k <= 109原站题解
cpp 解法, 执行用时: 117 ms, 内存消耗: 86.2 MB, 提交时间: 2024-04-07 22:26:12
class Solution {
public:
long long minOperationsToMakeMedianK2(vector<int> &nums, int k) {
ranges::sort(nums);
long long ans = 0;
int m = nums.size() / 2;
if (nums[m] > k) {
for (int i = m; i >= 0 && nums[i] > k; i--) {
ans += nums[i] - k;
}
} else {
for (int i = m; i < nums.size() && nums[i] < k; i++) {
ans += k - nums[i];
}
}
return ans;
}
// 快速选择
long long minOperationsToMakeMedianK(vector<int> &nums, int k) {
int m = nums.size() / 2;
ranges::nth_element(nums, nums.begin() + m);
long long ans = 0;
if (nums[m] > k) {
for (int i = 0; i <= m; i++) {
ans += max(nums[i] - k, 0);
}
} else {
for (int i = m; i < nums.size(); i++) {
ans += max(k - nums[i], 0);
}
}
return ans;
}
};
golang 解法, 执行用时: 122 ms, 内存消耗: 12.2 MB, 提交时间: 2024-04-07 22:25:30
func minOperationsToMakeMedianK(nums []int, k int) (ans int64) {
slices.Sort(nums)
m := len(nums) / 2
if nums[m] > k {
for i := m; i >= 0 && nums[i] > k; i-- {
ans += int64(nums[i] - k)
}
} else {
for i := m; i < len(nums) && nums[i] < k; i++ {
ans += int64(k - nums[i])
}
}
return
}
java 解法, 执行用时: 31 ms, 内存消耗: 61.3 MB, 提交时间: 2024-04-07 22:25:17
class Solution {
public long minOperationsToMakeMedianK(int[] nums, int k) {
Arrays.sort(nums);
long ans = 0;
int m = nums.length / 2;
if (nums[m] > k) {
for (int i = m; i >= 0 && nums[i] > k; i--) {
ans += nums[i] - k;
}
} else {
for (int i = m; i < nums.length && nums[i] < k; i++) {
ans += k - nums[i];
}
}
return ans;
}
}
python3 解法, 执行用时: 149 ms, 内存消耗: 39.4 MB, 提交时间: 2024-04-07 22:25:04
class Solution:
def minOperationsToMakeMedianK(self, nums: List[int], k: int) -> int:
nums.sort()
m = len(nums) // 2
ans = 0
if nums[m] > k:
for i in range(m, -1, -1):
if nums[i] <= k:
break
ans += nums[i] - k
else:
for i in range(m, len(nums)):
if nums[i] >= k:
break
ans += k - nums[i]
return ans