1338. Reduce Array Size to The Half — JavaScript

var minSetSize = function(arr) {
const map = new Map();

for (const num of arr) {
if (!map.has(num)) map.set(num, 0);
map.set(num, map.get(num) + 1);
}

// because javascript doesn't have built-in priority queue data structure, we need to just sort descending based on count to mimic maxHeap
const countPairs = [...map].sort((a, b) => b[1] - a[1]);

const target = arr.length / 2; // we know its even, so we don't have to worry about remainders

let index = 0;
let counts = 0;
let sum = 0;

while (sum < target) {
sum += countPairs[index++][1];
counts++;
}

return counts;
};

--

--

自學寫程式,目前爲 React 前端工程師。熱愛旅遊,將近 30 個國家,足跡遍佈亞洲與歐洲。生命與街舞已經離不開,歡迎訂閱 Youtube 頻道:https://www.youtube.com/channel/UCEU-bEDl7R-iGyLVZFae33g 。

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
黃韋智

自學寫程式,目前爲 React 前端工程師。熱愛旅遊,將近 30 個國家,足跡遍佈亞洲與歐洲。生命與街舞已經離不開,歡迎訂閱 Youtube 頻道:https://www.youtube.com/channel/UCEU-bEDl7R-iGyLVZFae33g