首页 > 编程学习 > LeetCode 2007. Find Original Array From Doubled Array

原题链接在这里:https://leetcode.com/problems/find-original-array-from-doubled-array/

题目:

An 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

题解:

Count the freq of each element.

Starting from smallest x, check if there are more 2x in the map.

To start from the smallest, we could use TreeMap.

Note: for(int j = 0; j < tm.get(x); j++) needs to be j < tm.get(x). tm.get(x) could be changed. e.g. changed = {0, 0, 0, 0}. the original is {0, 0}. tm.get(0) keeps changing in each loop iteration.

Time Complexity: O(nlogn). n = changed.length. 

Space: O(n).

AC Java:

 1 class Solution {
 2     public int[] findOriginalArray(int[] changed) {
 3         if(changed == null || changed.length % 2 == 1){
 4             return new int[0];
 5         }
 6         
 7         int n = changed.length;
 8         int [] res = new int[n / 2];
 9         TreeMap<Integer, Integer> tm = new TreeMap<>();
10         for(int num : changed){
11             tm.put(num, tm.getOrDefault(num, 0) + 1);
12         }
13         
14         int i = 0;
15         for(int x : tm.keySet()){
16             if(tm.get(x) > tm.getOrDefault(x + x, 0)){
17                 return new int[0];
18             }
19             
20             for(int j = 0; j < tm.get(x); j++){
21                 res[i++] = x;
22                 tm.put(x + x, tm.get(x + x) - 1);
23             }
24         }
25         
26         return res;
27     }
28 }

 

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号