### 题目描述 给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，返回 true；否则，返回 false。 ### 输入输出 #### 示例1 ``` 输入：arr = [3,1,3,6] 输出：false ``` #### 示例2 ``` 输入：arr = [2,1,2,6] 输出：false ``` #### 示例3 ``` 输入：arr = [4,-2,2,-4] 输出：true 解释：可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4] ``` ### 题目解答 #### 思路 题目主要就是一个配对问题，一个数字和它的二倍进行配对。对于较小的数字，它只能和数组里面大于他的进行配对，因此配对需要从小到大进行。同时由于有正数和负数，因此需要考虑数字的绝对值，按照绝对值大小从小到大进行配对操作。 **算法复杂度** 时间复杂度：需要遍历数组，查看每个数字都有多少个，然后需要对这些数字进行匹配，基本复杂度就是$$O(n)$$ 空间复杂度：最多需要n个位置记录，每个元素都有多少个，空间复杂度$$O(n)$$ #### 代码实现 在代码实现中，利用Conter快速实现对数组元素的计数 ```python class Solution: def canReorderDoubled(self, arr: List[int]) -> bool: cnt = Counter(arr) if cnt[0] % 2 == 1: return False for x in sorted(cnt, key=abs): if cnt[2*x] < cnt[x]: return False cnt[2*x] -= cnt[x] return True ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复