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

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

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

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)；

* 因此，总的空间复杂度为 O(log n)。

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

go完整代码如下：

代码语言：javascript复制

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

代码语言：javascript复制

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);
}

target 遍历 函数 排序 数组

0 人点赞