0954. Array of Doubled Pairs

题目信息

题号:

0954

难度:

Medium

主题:

数组、成对匹配、倍数关系

原题:

LeetCode 0954

重点:

需要把全部元素两两配对,使每对中一个数恰好是另一个数的两倍;负数、零和重复值都按各自出现次数参与匹配

题目重述

给定偶数长度的整数数组 arr。判断能否重新排列数组,使对于每个偶数下标 2 * i,都满足 arr[2 * i + 1] == 2 * arr[2 * i]。

等价地,需要把所有元素恰好划分为若干有序数值对 (x, 2x)。每个数组元素实例只能使用一次;数组可能包含负数、零和重复值。若可以完成配对返回 true,否则返回 false。

2 <= arr.length <= 3 * 10^4,数组长度为偶数,-10^5 <= arr[i] <= 10^5。

自建示例

负数也可以与其两倍配对:

输入:arr = [-2,-4,1,2]
输出:true
解释:可以重新排列为 [-2,-4,1,2],形成数值对 (-2,-4) 和 (1,2),每对第二个数都是第一个数的两倍。

零的数量无法两两配对:

输入:arr = [0,0,0,1]
输出:false
解释:两个 0 可以组成一对 (0,0),但剩余的 0 和 1 无法形成 (x,2x),因此不能使用全部元素。