LeetCode 솔루션 분류
[9/15] 2007. Find Original Array From Doubled Array
본문
Medium
163692Add to ListShareAn integer array original
is transformed into a doubled array changed
by appending twice the value of every element in original
, and then randomly shuffling the resulting array.
Given an array changed
, return original
if changed
is a doubled array. If changed
is not a doubled array, return an empty array. The elements in original
may be returned in any order.
Example 1:
Input: changed = [1,3,4,2,6,8] Output: [1,3,4] Explanation: One possible original array could be [1,3,4]: - Twice the value of 1 is 1 * 2 = 2. - Twice the value of 3 is 3 * 2 = 6. - Twice the value of 4 is 4 * 2 = 8. Other original arrays could be [4,3,1] or [3,1,4].
Example 2:
Input: changed = [6,3,0,1] Output: [] Explanation: changed is not a doubled array.
Example 3:
Input: changed = [1] Output: [] Explanation: changed is not a doubled array.
Constraints:
1 <= changed.length <= 105
0 <= changed[i] <= 105
Accepted
90,411
Submissions
221,593
태그
#Google
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 2829 ms, faster than 26.21% of Python3 online submissions for Find Original Array From Doubled Array.
Memory Usage: 33.3 MB, less than 21.38% of Python3 online submissions for Find Original Array From Doubled Array.
Memory Usage: 33.3 MB, less than 21.38% of Python3 online submissions for Find Original Array From Doubled Array.
from collections import Counter
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
if len(changed)%2: return []
changed = sorted(changed)
N = len(changed)
zero_counter = 0
while changed and changed[0] == 0:
changed.pop(0)
zero_counter+=1
if zero_counter%2: return []
og = [0]*(zero_counter//2)
counter = Counter(changed)
for key in sorted(counter.keys()):
if counter[key] == 0: continue
if counter[key*2] == 0: return []
counter[key*2] -= counter[key]
for key in counter.keys():
og += [key]*counter[key]
return og if len(og)*2 == N else []