leetcode1460：通过翻转子数组使两个数组相等（make-two-arrays-equal-by-reversing-subarrays）

carloscn commented 1 year ago

问题描述

给你两个长度相同的整数数组 target 和 arr 。每一步中，你可以选择 arr 的任意非空子数组并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。

示例 1：

输入：target = [1,2,3,4], arr = [2,4,1,3] 输出：true 解释：你可以按照如下步骤使 arr 变成 target： 1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3] 2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3] 3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4] 上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。

示例 2：

输入：target = [7], arr = [7] 输出：true 解释：arr 不需要做任何翻转已经与 target 相等。

示例 3：

输入：target = [3,7,9], arr = [3,7,11] 输出：false 解释：arr 没有数字 9 ，所以无论如何也无法变成 target 。

提示：

target.length == arr.length 1 <= target.length <= 1000 1 <= target[i] <= 1000 1 <= arr[i] <= 1000

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/make-two-arrays-equal-by-reversing-subarrays

carloscn commented 1 year ago

涉及知识

桶排序

我们很多人可能更多的熟悉冒泡排序、快速排序、归并排序。可能对堆排序、桶排序、计数排数等比较生疏，其实这个也没啥复杂的，桶排序是所有排序中最简单的排序之一。没毛病老铁，就是最简单的之一。并且桶排序和计数排序，基数排序有很多相似和渊源之处。

桶排序思想其实桶排序重要的是它的思想，而不是具体实现，桶排序从字面的意思上看：

桶：若干个桶，说明此类排序将数据放入若干个桶中。
桶：每个桶有容量，桶是有一定容积的容器，所以每个桶中可能有多个元素。
桶：从整体来看，整个排序更希望桶能够更匀称，即既不溢出(太多)又不太少。

但是这些桶跟排序又有什么关系呢？首先先说下桶排序的思想，百度百科是这么说的

工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。

用通俗易懂的话来理解：

将待排序的序列分到若干个桶中，每个桶内的元素再进行个别排序。
时间复杂度最好可能是线性O(n)，桶排序不是基于比较的排序

当然，桶排序是一种用空间换取时间的排序。

既然是排序，那么最终的结果肯定是从小到大的，桶排序借助桶的位置完成一次初步的排序——将待排序元素分别放至各个桶内。

而我们通常根据待排序元素整除的方法将其较为均匀的放至桶中，如8 5 22 15 28 9 45 42 39 19 27 47 12这个待排序序列，假设放入桶编号的规则为：n/10。这样首先各个元素就可以直接通过整除的方法放至对应桶中。而右侧所有桶内数据都比左侧的要大！

在刚刚放入桶中的时候，各个桶的大小相对可以确定，右侧都比左侧大，但桶内还是无序的，对各个桶内分别进行排序，再依次按照桶的顺序、桶内序列顺序得到一个最终排序的序列。

以上就是桶排序在算法上的思想了。如果使用java具体实现的话思路也很简单：用List[]类型的集合数组表示桶，每个List代表一个桶，将数据根据整除得到的值直接放到对应编号的集合里面去，再依次进行排序就可以了。

摘录：https://www.cnblogs.com/bigsai/p/13396391.html

carloscn commented 1 year ago

问题分析

对比两个无序数组是否相等，可以用桶计数的方法。也就是生成一个桶，桶的长度就是元素中的最大值，然后数组的值就是桶的坐标。两个数组一个涨一个消。如果桶内的数据全0那就说明是一样的。（只适用于数组值不大的两个数组）

pub fn can_be_equal(target: Vec<i32>, arr: Vec<i32>) -> bool
{
    if target.is_empty() ||
       target.len() != arr.len() {
        return true;
    }

    let max_len:i32 = *target.iter().max().unwrap();
    if max_len != *arr.iter().max().unwrap() {
        return false;
    }

    let mut dup_target:Vec<i32> = vec![0; max_len as usize + 1];

    for i in 0..target.len() {
        dup_target[target[i] as usize] += 1;
        dup_target[arr[i] as usize] -= 1;
    }

    for i in 0..target.len() {
        if dup_target[i] != 0 {
            return false;
        }
    }

    return true;
}

carloscn commented 1 year ago

code

https://review.gerrithub.io/c/carloscn/structstudy/+/554486 https://github.com/carloscn/structstudy/commit/da6d4d3b7e983879ed97e9c014b372dd3249ebe6

carloscn / structstudy