1338. Reduce Array Size to The Half

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

大意：選出最少刪掉幾個數字可以把數組長度減去一半
思路：

1. 遍歷數組，將數字出現的次數記錄下來
2. 根據出現次數排序
3. 減去次數，確認剩餘數量

前面步驟一都是一樣的，使用Map來記錄次數

let size = arr.length;
    const record = new Map();
    for (const i of arr) {
        if (record.has(i)) {
            record.set(i, record.get(i) + 1);
        } else {
            record.set(i, 1);
        }
    }

排序有很多種作法

1. 直接把map轉換成數組
   注意轉換方式 Array.from(record);
   這樣會把map轉換成二維數組，形如[[key, value], [key, value], ... ]

   const toArray = Array.from(record);
   toArray.sort(function(a,b) {return b[1] - a[1]});
   for (let i = 0; i < toArray.length; i++) {
      size -= toArray[i][1];
      if (size <= arr.length / 2) {
          return i + 1;
      }
   }
   

2. 因為不在乎實際要刪的是什麼數，只要遍歷map把出現次數記下來就好
   注意map的forEach是 (val, key)

    const count = [];
    record.forEach((val, key) => {
        count.push(val);
    })
    count.sort(function(a,b){return b-a});
    for (let i = 0; i < count.length; i++) {
        size -= count[i];
        if (size <= arr.length / 2) {
            return i + 1;
        }
    }
   };
   

   整段代碼:

   /**
   * @param {number[]} arr
   * @return {number}
   */
   var minSetSize = function(arr) {
    let size = arr.length;
    const record = new Map();
    for (const i of arr) {
        if (record.has(i)) {
            record.set(i, record.get(i) + 1);
        } else {
            record.set(i, 1);
        }
    }
    // const toArray = Array.from(record);
    // toArray.sort(function(a,b) {return b[1] - a[1]});
    // for (let i = 0; i < toArray.length; i++) {
    //     size -= toArray[i][1];
    //     if (size <= arr.length / 2) {
    //         return i + 1;
    //     }
    // }
    const count = [];
    record.forEach((val, key) => {
        count.push(val);
    })
    count.sort(function(a,b){return b-a});
    for (let i = 0; i < count.length; i++) {
        size -= count[i];
        if (size <= arr.length / 2) {
            return i + 1;
        }
    }
   };