2022-04-22：给你两个正整数数组 nums 和 target ，两个数组长度相等。在一次操作中，你可以选择两个不同的下标 i 和 j ，其中 0 ＜= i, j ＜ nums.leng

2023-04-22
北京
本文字数：1844 字
阅读完需：约 6 分钟

2022-04-22：给你两个正整数数组 nums 和 target ，两个数组长度相等。在一次操作中，你可以选择两个不同的下标 i 和 j ，其中 0 <= i, j < nums.length ，并且：令 nums[i] = nums[i] + 2 且令 nums[j] = nums[j] - 2 。如果两个数组中每个元素出现的频率相等，我们称两个数组是相似的。请你返回将 nums 变得与 target 相似的最少操作次数。测试数据保证 nums 一定能变得与 target 相似。输入：nums = [8,12,6], target = [2,14,10]。输出：2。

答案 2022-04-22：

给定两个长度相等的整型数组 nums 和 target，要求将 nums 变为与 target 相似，并返回最少需要的操作次数。

具体地，每一次操作可以选择两个下标 i 和 j，并满足以下条件：

0 <= i,j < nums.length
nums[i] = nums[i] + 2，nums[j] = nums[j] - 2

操作后，需要检查变换后的 nums 是否与 target 频率相等。如果是，则称 nums 与 target 是相似的，返回此时的操作次数。

按照题目描述实现过程可以分为以下几个步骤：

统计 nums 和 target 中所有元素出现的频率，然后比较两者是否相同。由于题目保证了 nums 可以变为 target 相似，因此这一步可以省略。
对 nums 和 target 进行奇偶数值分离，将奇数值从偶数值中分离出来。这一步可以使用 split() 函数实现。
对 nums 和 target 分别对奇数值和偶数值进行排序。这里可以使用 sort.Ints() 函数进行排序。
逐一比较 nums 和 target 中的对应元素，计算它们之间的差值的绝对值之和。这一步可以使用 abs() 函数和循环实现。
将差值的绝对值之和除以 4，即得到最少操作次数。

整个过程就是这样。具体来说，第二步和第三步是为了方便后面的比较和计算而进行的预处理。第四步是最重要的一步，需要仔细计算每一个位置上的差值，并将它们相加。第五步只是简单的除法运算，将计算结果转化为操作次数即可。

时间复杂度：

对于奇偶数值分离的操作，需要遍历一遍数组，时间复杂度为 $O (n)$ ；
对于排序操作和差值计算操作，需要遍历两次长度为 $n$ 的数组，时间复杂度为 $O (n lo g n)$ ；
因此，总的时间复杂度为 $O (n lo g n)$ 。

空间复杂度：

变量 numsOddSize、line 和 ans 占用常数级别的空间，不随输入规模变化，因此空间复杂度为 O(1)；
函数中使用了 sort.Ints() 函数进行排序，该函数使用了快速排序算法，在最坏情况下需要递归调用 log_2(n) 层，空间复杂度为 O(log n)；
因此，总的空间复杂度为 O\log n)。

综上所述，该算法的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。

go 完整代码如下：

package main
import (  "fmt"  "sort")
func makeSimilar(nums, target []int) int64 {  n := len(nums)  numsOddSize := split(nums)  split(target)  sort.Ints(nums[:numsOddSize])  sort.Ints(nums[numsOddSize:])  sort.Ints(target[:numsOddSize])  sort.Ints(target[numsOddSize:])
  var ans int64  for i := 0; i < n; i++ {    ans += int64(abs(nums[i] - target[i]))  }  return ans >> 2}
func split(arr []int) int {  line := 0  for i := 0; i < len(arr); i++ {    if arr[i]&1 != 0 {      swap(arr, i, line)      line++    }  }  return line}
func swap(arr []int, i, j int) {  tmp := arr[i]  arr[i] = arr[j]  arr[j] = tmp}
func abs(x int) int {  if x < 0 {    return -x  }  return x}
func main() {  nums := []int{8, 12, 6}  target := []int{2, 14, 10}  ans := makeSimilar(nums, target)  fmt.Println(ans)}

复制代码

rust 完整代码如下：

fn make_similar(nums: Vec<i32>, target: Vec<i32>) -> i64 {    let n = nums.len();    let mut nums = nums;    let mut target = target;
    let odd_size = split(&mut nums);    split(&mut target);    nums[..odd_size].sort_unstable();    nums[odd_size..n].sort_unstable();    target[..odd_size].sort_unstable();    target[odd_size..n].sort_unstable();
    let mut ans = 0;    for i in 0..n {        ans += (nums[i] - target[i]).abs() as i64;    }    ans >> 2}
fn split(arr: &mut [i32]) -> usize {    let mut line = 0;    for i in 0..arr.len() {        if arr[i] & 1 != 0 {            arr.swap(i, line);            line += 1;        }    }    line}
fn main() {    let nums = vec![8, 12, 6];    let target = vec![2, 14, 10];    let ans = make_similar(nums, target);    println!("{}", ans);}