0954._Array_of_Doubled_Pairs.md

954. Array of Doubled Pairs

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

先sort

例如[4,-2,2,-4]，sort后变成[-4,-2,2,4]

开始遍历

• num小于0说明要check num/2是否在A中，因为后面的负数的绝对值只会比num小
• num大于0说明要check num*2是否在A中，因为后面的正数只会比num大
• num等于0就需要看后面还有没有0了

实现中用一个dele来记录哪些数字已经被删除过多少次了

class Solution:
    def canReorderDoubled(self, A):
        """
        :type A: List[int]
        :rtype: bool
        """
        if not A or len(A) == 0:
            return True
        
        A.sort()
        lookup = collections.Counter(A)
        dele = collections.Counter([])
        
        for i in range(0, len(A)):
            if dele[A[i]] > 0: # 如果num已经被删除过一次了，那么要直接跳过它，更新被删除的频次
                dele[A[i]] -= 1
                continue
            if A[i] < 0: # num小于0说明要check num/2是否在A中
                if A[i] % 2 == 1:
                    return False
                if lookup[A[i]/2] <= 0:
                    return False
                lookup[A[i]] -= 1
                lookup[A[i]/2] -= 1
                dele[A[i]/2] += 1
            elif A[i] == 0:
                lookup[0] -= 2
                if lookup[0] < 0:
                    return False
                dele[0] += 1
            else:        # num大于0说明要check num*2是否在A中
                if lookup[2*A[i]] <= 0:
                    return False
                lookup[A[i]] -= 1
                lookup[2*A[i]] -= 1
                dele[A[i]*2] += 1
                
        return all(lookup[key] == 0 for key in lookup)