66import java .util .List ;
77import java .util .Map ;
88
9- /**
10- * 1338. Reduce Array Size to The Half
11- *
12- * Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
13- * Return the minimum size of the set so that at least half of the integers of the array are removed.
14- *
15- * Example 1:
16- * Input: arr = [3,3,3,3,5,5,5,2,2,7]
17- * Output: 2
18- * Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
19- * Possible sets of size 2 are {3,5},{3,2},{5,2}.
20- * Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.
21- *
22- * Example 2:
23- * Input: arr = [7,7,7,7,7,7]
24- * Output: 1
25- * Explanation: The only possible set you can choose is {7}. This will make the new array empty.
26- *
27- * Example 3:
28- * Input: arr = [1,9]
29- * Output: 1
30- *
31- * Example 4:
32- * Input: arr = [1000,1000,3,7]
33- * Output: 1
34- *
35- * Example 5:
36- * Input: arr = [1,2,3,4,5,6,7,8,9,10]
37- * Output: 5
38- *
39- * Constraints:
40- * 1 <= arr.length <= 10^5
41- * arr.length is even.
42- * 1 <= arr[i] <= 10^5
43- * */
449public class _1338 {
4510public static class Solution1 {
4611public int minSetSize (int []arr ) {
@@ -61,4 +26,28 @@ public int minSetSize(int[] arr) {
6126return i --;
6227 }
6328 }
29+
30+ public static class Solution2 {
31+ public int minSetSize (int []arr ) {
32+ Map <Integer ,Integer >map =new HashMap <>();
33+ for (int num :arr ) {
34+ map .put (num ,map .getOrDefault (num ,0 ) +1 );
35+ }
36+ List <int []>list =new ArrayList <>();
37+ for (int key :map .keySet ()) {
38+ list .add (new int []{map .get (key ),key });
39+ }
40+ Collections .sort (list , (a ,b ) ->b [0 ] -a [0 ]);
41+ int minSet =0 ;
42+ int count =0 ;
43+ for (int []pair :list ) {
44+ count +=pair [0 ];
45+ minSet ++;
46+ if (count >=arr .length /2 ) {
47+ return minSet ;
48+ }
49+ }
50+ return minSet ;
51+ }
52+ }
6453}