【leetcode】954. Array of Doubled Pairs

题目如下：

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.
Example 1:
Input: [3,1,3,6]

Output: false
Example 2:
Input: [2,1,2,6]

Output: false
Example 3:
Input: [4,-2,2,-4]

Output: true

Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].
Example 4:
Input: [1,2,4,16,8,4]

Output: false
Note:

0 <= A.length <= 30000

A.length is even

-100000 <= A[i] <= 100000

解题思路：本题难度不大，思路也非常简单。遍历A，同时用字典dic记录A中每个元素出现的次数，如果A[i] 是偶数并且A[i]/2存在于dic中，那么把A[i]/2在dic中出现的次数减去1，如果出现次数降为0，从dic中删除该key值；否则继续判断A[i]*2是否存在于dic中；如果两个条件都不满足，把A[i]加入dic中。最后判断dic的长度是否为0即可，

代码如下：

class Solution(object):

    def canReorderDoubled(self, A):

        """

        :type A: List[int]

        :rtype: bool

        """

        A.sort()

        dic = {}

        for i in A:

            if i % 2 == 0 and i/2 in dic:

                i = i / 2

                dic[i] -= 1

                if dic[i] == 0:

                    del dic[i]

            elif i * 2 in dic:

                i = i * 2

                dic[i] -= 1

                if dic[i] == 0:

                    del dic[i]

            else:

                dic[i] = dic.setdefault(i, 0) + 1

                continue

        return len(dic) == 0

巴特西

【leetcode】954. Array of Doubled Pairs

最新文章

热门文章