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

2022-04-22：给你两个正整数数组 nums 和 target ，两个数组长度相等。

在一次操作中，你可以选择两个 不同 的下标 i 和 j ，

其中 0 <= i, j < nums.length ，并且：

令 numsi = numsi 2 且

令 numsj = numsj - 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 是相似的，返回此时的操作次数。

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

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

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

时间复杂度：

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

空间复杂度：

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

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

go完整代码如下：

代码语言：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完整代码如下：

代码语言：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);
}

在这里插入图片描述

编程算法算法 go rust

0 人点赞