class Solution {
public:
long long makeSimilar(vector<int>& nums, vector<int>& target) {
}
};
2449. 使数组相似的最少操作次数
给你两个正整数数组 nums 和 target ，两个数组长度相等。
在一次操作中，你可以选择两个 不同 的下标 i 和 j ，其中 0 <= i, j < nums.length ，并且：
nums[i] = nums[i] + 2 且nums[j] = nums[j] - 2 。如果两个数组中每个元素出现的频率相等，我们称两个数组是 相似 的。
请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。
示例 1：
输入：nums = [8,12,6], target = [2,14,10] 输出：2 解释：可以用两步操作将 nums 变得与 target 相似： - 选择 i = 0 和 j = 2 ，nums = [10,12,4] 。 - 选择 i = 1 和 j = 2 ，nums = [10,14,2] 。 2 次操作是最少需要的操作次数。
示例 2：
输入：nums = [1,2,5], target = [4,1,3] 输出：1 解释：一步操作可以使 nums 变得与 target 相似： - 选择 i = 1 和 j = 2 ，nums = [1,4,3] 。
示例 3：
输入：nums = [1,1,1,1,1], target = [1,1,1,1,1] 输出：0 解释：数组 nums 已经与 target 相似。
提示：
n == nums.length == target.length1 <= n <= 1051 <= nums[i], target[i] <= 106nums 一定可以变得与 target 相似。原站题解
golang 解法, 执行用时: 192 ms, 内存消耗: 9.1 MB, 提交时间: 2023-05-24 09:57:10
func f(a []int) {
for i, x := range a {
if x%2 > 0 {
a[i] = -x // 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
}
}
sort.Ints(a)
}
func makeSimilar(nums, target []int) (ans int64) {
f(nums)
f(target)
for i, x := range nums {
ans += int64(abs(x - target[i]))
}
return ans / 4
}
func abs(x int) int { if x < 0 { return -x }; return x }
java 解法, 执行用时: 42 ms, 内存消耗: 54.8 MB, 提交时间: 2023-05-24 09:56:53
class Solution {
public long makeSimilar(int[] nums, int[] target) {
f(nums);
f(target);
var ans = 0L;
for (var i = 0; i < nums.length; ++i)
ans += Math.abs(nums[i] - target[i]);
return ans / 4;
}
private void f(int[] a) {
// 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
for (var i = 0; i < a.length; ++i)
if (a[i] % 2 != 0) a[i] = -a[i];
Arrays.sort(a);
}
}
python3 解法, 执行用时: 828 ms, 内存消耗: 34.1 MB, 提交时间: 2023-05-24 09:56:34
def f(a: List[int]) -> None:
for i, x in enumerate(a):
if x % 2: a[i] = -x # 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
a.sort()
class Solution:
def makeSimilar(self, nums: List[int], target: List[int]) -> int:
f(nums)
f(target)
return sum(abs(x - y) for x, y in zip(nums, target)) // 4
python3 解法, 执行用时: 1080 ms, 内存消耗: 40.3 MB, 提交时间: 2023-05-24 09:56:08
class Solution:
def makeSimilar(self, nums: List[int], target: List[int]) -> int:
nums.sort(key=lambda x:(x%2,x))
target.sort(key = lambda x:(x%2,x))
return sum(nums[i] - target[i] for i in range(len(nums)) if nums[i] > target[i])//2