Skip to content

Commit d0e7d4b

Browse files
fishercoder1534fishercoder1534
committed
add 1356
1 parent d8ca070 commit d0e7d4b

File tree

3 files changed

+113
-0
lines changed

3 files changed

+113
-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+
|1356|[Sort Integers by The Number of 1 Bits](https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1356.java) | |Easy|Sort, Bit Manipulation|
1112
|1354|[Construct Target Array With Multiple Sums](https://leetcode.com/problems/construct-target-array-with-multiple-sums/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1354.java) | |Hard|Greedy|
1213
|1353|[Maximum Number of Events That Can Be Attended](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1353.java) | |Medium|Greedy, Sort, Segment Tree|
1314
|1352|[Product of the Last K Numbers](https://leetcode.com/problems/product-of-the-last-k-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1352.java) | |Medium|Array, Design|

‎src/main/java/com/fishercoder/solutions/_1356.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.HashMap;
6+
import java.util.List;
7+
import java.util.Map;
8+
9+
/**
10+
* 1356. Sort Integers by The Number of 1 Bits
11+
*
12+
* Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1's in
13+
* their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.
14+
*
15+
* Return the sorted array.
16+
*
17+
* Example 1:
18+
* Input: arr = [0,1,2,3,4,5,6,7,8]
19+
* Output: [0,1,2,4,8,3,5,6,7]
20+
* Explantion: [0] is the only integer with 0 bits.
21+
* [1,2,4,8] all have 1 bit.
22+
* [3,5,6] have 2 bits.
23+
* [7] has 3 bits.
24+
* The sorted array by bits is [0,1,2,4,8,3,5,6,7]
25+
*
26+
* Example 2:
27+
* Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
28+
* Output: [1,2,4,8,16,32,64,128,256,512,1024]
29+
* Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.
30+
*
31+
* Example 3:
32+
* Input: arr = [10000,10000]
33+
* Output: [10000,10000]
34+
*
35+
* Example 4:
36+
* Input: arr = [2,3,5,7,11,13,17,19]
37+
* Output: [2,3,5,17,7,11,13,19]
38+
*
39+
* Example 5:
40+
* Input: arr = [10,100,1000,10000]
41+
* Output: [10,100,10000,1000]
42+
*
43+
* Constraints:
44+
* 1 <= arr.length <= 500
45+
* 0 <= arr[i] <= 10^4
46+
* */
47+
public class _1356 {
48+
public static class Solution1 {
49+
public int[] sortByBits(int[] arr) {
50+
Map<Integer, List<Integer>> map = new HashMap<>();
51+
for (int num : arr) {
52+
int count = Integer.bitCount(num);
53+
if (!map.containsKey(count)) {
54+
map.put(count, new ArrayList<>());
55+
}
56+
map.get(count).add(num);
57+
}
58+
int[] result = new int[arr.length];
59+
int i = 0;
60+
for (int count : map.keySet()) {
61+
List<Integer> list = map.get(count);
62+
Collections.sort(list);
63+
for (int num : list) {
64+
result[i++] = num;
65+
}
66+
}
67+
return result;
68+
}
69+
}
70+
}

‎src/test/java/com/fishercoder/_1356Test.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1356;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertArrayEquals;
8+
9+
public class _1356Test {
10+
private static _1356.Solution1 solution1;
11+
12+
@BeforeClass
13+
public static void setup() {
14+
solution1 = new _1356.Solution1();
15+
}
16+
17+
@Test
18+
public void test1() {
19+
assertArrayEquals(new int[]{0, 1, 2, 4, 8, 3, 5, 6, 7}, solution1.sortByBits(new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8}));
20+
}
21+
22+
@Test
23+
public void test2() {
24+
assertArrayEquals(new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}, solution1.sortByBits(new int[]{1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}));
25+
}
26+
27+
@Test
28+
public void test3() {
29+
assertArrayEquals(new int[]{10000, 10000}, solution1.sortByBits(new int[]{10000, 10000}));
30+
}
31+
32+
@Test
33+
public void test4() {
34+
assertArrayEquals(new int[]{2, 3, 5, 17, 7, 11, 13, 19}, solution1.sortByBits(new int[]{2, 3, 5, 7, 11, 13, 17, 19}));
35+
}
36+
37+
@Test
38+
public void test5() {
39+
assertArrayEquals(new int[]{10, 100, 10000, 1000}, solution1.sortByBits(new int[]{10, 100, 1000, 10000}));
40+
}
41+
42+
}

0 commit comments

Comments
 (0)