1338. Reduce Array Size to The Half

leetcode medium

#array#csharp#hash-table#leetcode#medium#sort

Task

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

Верните минимальный размер набора, чтобы было удалено не менее половины целых чисел из массива.

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]

Output: 2

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).

Possible sets of size 2 are {3,5},{3,2},{5,2}.

Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

C# solution

matched/original

public class Solution {
    public int MinSetSize(int[] arr) {
        Array.Sort(arr);
        
        List<int> counts = new List<int>();
        int currentRun = 1;
        for (int i = 1; i < arr.Length; i++) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.Add(currentRun);
            currentRun = 1;
        }
        counts.Add(currentRun);
        
        counts.Sort((a, b) => b.CompareTo(a));
        
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        foreach (int count in counts) {
            numbersRemovedFromArr += count;
            setSize += 1;   
            if (numbersRemovedFromArr >= arr.Length / 2) {
                break;
            }
        }
        
        return setSize;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSetSize(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        
        List<int> counts = new List<int>();
        int currentRun = 1;
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.push_back(currentRun);
            currentRun = 1;
        }
        counts.push_back(currentRun);
        
        counts.Sort((a, b) => b.CompareTo(a));
        
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        foreach (int count in counts) {
            numbersRemovedFromArr += count;
            setSize += 1;   
            if (numbersRemovedFromArr >= arr.size() / 2) {
                break;
            }
        }
        
        return setSize;
    }
}

Java solution

matched/original

class Solution {
    public int minSetSize(int[] arr) {
        Arrays.sort(arr);
        List<Integer> counts = new ArrayList<>();
        int currentRun = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1;
                continue;
            }
            counts.add(currentRun);
            currentRun = 1;
        }
        counts.add(currentRun);
        Collections.sort(counts);
        Collections.reverse(counts);
        int numbersRemovedFromArr = 0;
        int setSize = 0;
        for (int count : counts) {
            numbersRemovedFromArr += count;
            setSize += 1;
            if (numbersRemovedFromArr >= arr.length / 2) {
                break;
            }
        }
        return setSize;
    }
}

Python solution

matched/original

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        arr.sort()
        
        counts = []
        current_run = 1
        for i in range(1, len(arr)):
            if arr[i] == arr[i - 1]:
                current_run += 1
                continue
            counts.append(current_run)
            current_run = 1
        counts.append(current_run)
        
        counts.sort(reverse=True)
        
        numbers_removed_from_arr = 0
        set_size = 0
        for count in counts:
            numbers_removed_from_arr += count
            set_size += 1   
            if numbers_removed_from_arr >= len(arr) // 2:
                break
        
        return set_size

Explanation

Algorithm

Отсортировать массив и создать список подсчета количества вхождений каждого числа.

Отсортировать список подсчета в порядке убывания.

Удалять числа из массива, начиная с наибольшего количества вхождений, пока не будет удалено не менее половины чисел массива. Вернуть размер множества удаленных чисел.

😎