https://leetcode.com/problems/make-two-arrays-equal-by-reversing-subarrays
1460. Make Two Arrays Equal by Reversing Subarrays
给定arr跟target两个等长array 你可以任意反转arr的非空子阵列
反转不限次数
假设能让arr变成target 回传True 反之False
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
思路:
时间O(N) 空间O(N)
确认arr所有元素是否在target 然后确认数量是否相等
Python Code:
class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
record1 = defaultdict(int)
record2 = defaultdict(int)
for i in range(len(arr)):
if arr[i] not in target:
return False
record1[arr[i]] += 1
record2[target[i]] += 1
for k in record1.keys():
if record1[k] != record2[k]:
return False
return True
思路2:
时间O(nlogn) 空间O(1)
排序
Python Code:
class Solution:
def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
return sorted(target) == sorted(arr)