1460. 通过翻转子数组使两个数组相等

🟢   🔖  数组 哈希表 排序  🔗 力扣 LeetCode

题目

You are given two integer arrays of equal length target and arr. In one step, you can select any non-empty subarray of arr and reverse it. You are allowed to make any number of steps.

Return true if you can makearr equal totarget _ or _falseotherwise.

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]

Output: true

Explanation: You can follow the next steps to convert arr to target:

1- Reverse subarray [2,4,1], arr becomes [1,4,2,3]

2- Reverse subarray [4,2], arr becomes [1,2,4,3]

3- Reverse subarray [4,3], arr becomes [1,2,3,4]

There are multiple ways to convert arr to target, this is not the only way to do so.

Example 2:

Input: target = [7], arr = [7]

Output: true

Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]

Output: false

Explanation: arr does not have value 9 and it can never be converted to target.

Constraints:

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

题目大意

给你两个长度相同的整数数组 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

解题思路

问题要求判断是否可以通过任意次数组元素的交换使 arr 转换为 target。这种情况等价于检查两个数组中每个数字出现的次数是否完全相同。

思路一：哈希表

1. 统计 target 中每个数字的频次:

   • 使用一个 Map 来存储数字及其出现的次数。

2. 更新频次:

   • 遍历 arr，对每个数字对应的计数减 1。

3. 验证频次是否平衡:

   • 检查 Map 中所有的值是否都为 0，若不是，则两个数组不能通过交换等价。

复杂度分析

• 时间复杂度: O(n)，其中 n 是数组长度，遍历 target 和 arr。
• 空间复杂度: O(n)，需要存储 Map，占用的空间与数字种类的数量成正比。

---

思路二：排序

也可以通过排序的方式实现同样的效果。

• 对 target 和 arr 分别进行排序。
• 比较排序后的数组转成字符串后，是否相等。

复杂度分析

• 时间复杂度: O(n log n) (排序)
• 空间复杂度: O(1) (排序原地操作)

代码

哈希表

/**
 * @param {number[]} target
 * @param {number[]} arr
 * @return {boolean}
 */
var canBeEqual = function (target, arr) {
	let count = new Map();
	for (let num of target) {
		count.set(num, (count.get(num) || 0) + 1);
	}

	for (let num of arr) {
		count.set(num, (count.get(num) || 0) - 1);
	}

	for (let value of count.values()) {
		if (value !== 0) return false;
	}
	return true;
};

排序

var canBeEqual = function (target, arr) {
	target.sort((a, b) => a - b);
	arr.sort((a, b) => a - b);
	return target.join() === arr.join();
};