Skip to content

Commit 2a61df3

Browse files
add 2007
1 parent 2467f62 commit 2a61df3

File tree

3 files changed

+72
-0
lines changed

3 files changed

+72
-0
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★
88

99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
11+
|2007|[Find Original Array From Doubled Array](https://leetcode.com/problems/find-original-array-from-doubled-array/)|[Python3](../master/python3/2001.py), [Java](../master/src/main/java/com/fishercoder/solutions/_2007.java) ||Medium||
1112
|2006|[Count Number of Pairs With Absolute Difference K](https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/)|[Python3](../master/python3/2001.py), [Java](../master/src/main/java/com/fishercoder/solutions/_2006.java) ||Easy||
1213
|2001|[Number of Pairs of Interchangeable Rectangles](https://leetcode.com/problems/number-of-pairs-of-interchangeable-rectangles/)|[Python3](../master/python3/2001.py), [Java](../master/src/main/java/com/fishercoder/solutions/_2001.java) ||Medium||
1314
|2000|[Reverse Prefix of Word](https://leetcode.com/problems/reverse-prefix-of-word/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_2000.java) ||Easy||
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Arrays;
4+
import java.util.HashMap;
5+
import java.util.Map;
6+
7+
public class _2007 {
8+
public static class Solution1 {
9+
public int[] findOriginalArray(int[] changed) {
10+
if (changed.length % 2 != 0) {
11+
return new int[]{};
12+
}
13+
Arrays.sort(changed);
14+
int[] ans = new int[changed.length / 2];
15+
int k = 0;
16+
Map<Integer, Integer> map = new HashMap<>();
17+
for (int i = 0; i < changed.length; i++) {
18+
map.put(changed[i], map.getOrDefault(changed[i], 0) + 1);
19+
}
20+
for (int i = changed.length - 1; i >= 0; i--) {
21+
int doubledNumber = changed[i];
22+
if (map.containsKey(doubledNumber)) {
23+
int doubledNumberCount = map.get(doubledNumber);
24+
int halfNumber = doubledNumber / 2;
25+
if (!map.containsKey(halfNumber) || map.get(halfNumber) < doubledNumberCount || halfNumber * 2 != doubledNumber) {
26+
return new int[]{};
27+
} else {
28+
if (doubledNumber == halfNumber && map.get(halfNumber) % 2 == 0) {
29+
doubledNumberCount /= 2;
30+
while (doubledNumberCount-- > 0) {
31+
ans[k++] = halfNumber;
32+
}
33+
map.remove(halfNumber);
34+
} else {
35+
map.put(halfNumber, map.get(halfNumber) - doubledNumberCount);
36+
if (map.get(halfNumber) == 0) {
37+
map.remove(halfNumber);
38+
}
39+
while (doubledNumberCount-- > 0) {
40+
ans[k++] = halfNumber;
41+
}
42+
map.remove(doubledNumber);
43+
}
44+
}
45+
}
46+
}
47+
return ans;
48+
}
49+
}
50+
}
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._2007;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
public class _2007Test {
9+
private static _2007.Solution1 solution1;
10+
11+
@BeforeClass
12+
public static void setup() {
13+
solution1 = new _2007.Solution1();
14+
}
15+
16+
@Test
17+
public void test1() {
18+
CommonUtils.printArray(solution1.findOriginalArray(new int[]{1, 3, 4, 2, 6, 8}));
19+
}
20+
21+
}

0 commit comments

Comments
 (0)