Re: [閒聊] 每日LeetCode
2007. Find Original Array From Doubled Array
題目：給定一個陣列，若該陣列可以由某個陣列的所有元素乘2之後組合成，我們
說這個陣列是一個 Doubled Array，找出這個陣列是否是 Doubled Array 若存在則
返回該陣列變成 Doubled Arraay前的陣列。
Example:
[1,3,4] => [1,3,4,2,6,8]
思路：
1.先排序整個陣列讓每次遍歷時都從最小開始拿，避免：[2, 4, 2, 1] 這種 Case
會 2 -> 2 且 4 -> 1。
2.統計 Doubled Array 內的所有元素個數儲存在HashMap。
3.遍歷Double dArray的每個元素，若HashMap存在該元素則該元素和兩倍的該元素數量
減一，把該元素儲存在 List 中。
4.檢查HashMap所有元素的數量，若全為0表示每個元素都相互匹配，將List轉為int[]
返回，若任意元素不為0表示不匹配，返回空的int[]。
Java Code：
class Solution {
public int[] findOriginalArray(int[] nums) {
int n = nums.length;
if(n % 2 == 1) return new int[0];
Arrays.sort(nums);
Map<Integer, Integer> map = new HashMap<>();
for(int num : nums)
map.put(num ,map.getOrDefault(num,0) + 1);
List<Integer> list = new ArrayList<>();
for (int num : nums) {
int doubleChanged = num * 2;
if (map.containsKey(doubleChanged) && map.get(num) > 0) {
list.add(num);
map.put(num, map.get(num) - 1);
map.put(doubleChanged, map.get(doubleChanged) - 1);
}
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() != 0)
return new int[0];
}
int[] res = new int[list.size()];
int i = 0;
for(int num : list)
res[i++] = num;
return res;
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.59.138 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1663215351.A.7AA.html
推
09/15 12:18,
1年前
, 1F
09/15 12:18, 1F
→
09/15 12:31,
1年前
, 2F
09/15 12:31, 2F
→
09/15 12:31,
1年前
, 3F
09/15 12:31, 3F
討論串 (同標題文章)