[leetcode] 954. Array of Doubled Pairs

[leetcode] 954. Array of Doubled Pairs

Description

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: trueExplanation: 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 <= 30000A.length is even-100000 <= A[i] <= 100000

分析

题目的意思是：这道题是给数组排序，按照2划分，使得后一个数时前一个数的两倍。我自己尝试写了一下，没写出来，发现败给了abs和counter两个函数，自己的思路也不是很清晰。答案先统计了每个词的词频，然后把A又排序了一下之后进行遍历，每遍历一个数x，对应的频率-1，2x数的频率减1，如果2x本身就是0，说明已经用完了，找不到2*x，就不能构成满足条件的数组了，自然返回False。如果能够遍历完就返回True了，说明所有的数满足要求了啊。

代码

class Solution: def canReorderDoubled(self, A: List[int]) -> bool: counter=collections.Counter(A) for x in sorted(A,key=abs): if(counter[x]==0): continue elif(counter[2*x]==0): return False counter[x]-=1 counter[2*x]-=1 return True

参考文献

​​[LeetCode] Approach 1: Greedy​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。