题目链接:954. 二倍数对数组
暴力解法。
从绝对值最小的数字开始遍历,每次从列表中去掉当前元素和值为其二倍的另一个元素。如果无法成功操作,那么该数组不满足条件。如果最终能够去掉列表中的所有数,那该数组满足条件。
使用有序的列表,以及一个多重集合可以优化算法的时间复杂度。
from typing import List
from sortedcontainers import SortedList
class Solution:
def canReorderDoubled(self, arr: List[int]) -> bool:
arr = SortedList(arr, key=abs)
while len(arr) > 0:
minn = arr[0]
arr.remove(minn)
if (2 * minn) not in arr:
return False
arr.remove(2 * minn)
return True