954. 二倍数对数组

exiaohu 于 2022-04-01 发布

题目链接: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