feat: add No.1481

BaffinLee · BaffinLee · commit 5f86aa77a148 · 2024-02-16T23:24:52.000+08:00
diff --git a/1401-1500/1481. Least Number of Unique Integers after K Removals.md b/1401-1500/1481. Least Number of Unique Integers after K Removals.md
@@ -0,0 +1,114 @@
+# 1481. Least Number of Unique Integers after K Removals
+
+- Difficulty: Medium.
+- Related Topics: Array, Hash Table, Greedy, Sorting, Counting.
+- Similar Questions: .
+
+## Problem
+
+Given an array of integers `arr` and an integer `k`. Find the **least number of unique integers** after removing **exactly** `k` elements**.**
+
+
+
+
+ 
+Example 1:
+
+```
+Input: arr = [5,5,4], k = 1
+Output: 1
+Explanation: Remove the single 4, only 5 is left.
+```
+Example 2:
+
+```
+Input: arr = [4,3,1,1,3,3,2], k = 3
+Output: 2
+Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
+```
+
+ 
+**Constraints:**
+
+
+	
+- `1 <= arr.length <= 10^5`
+	
+- `1 <= arr[i] <= 10^9`
+	
+- `0 <= k <= arr.length`
+
+
+## Solution 1
+
+```javascript
+/**
+ * @param {number[]} arr
+ * @param {number} k
+ * @return {number}
+ */
+var findLeastNumOfUniqueInts = function(arr, k) {
+    var map = {};
+    for (var i = 0; i < arr.length; i++) {
+        map[arr[i]] = (map[arr[i]] || 0) + 1;
+    }
+    var nums = Array.from(Object.values(map));
+    nums.sort((a, b) => a - b);
+    while (k > 0 && nums.length && k >= nums[0]) {
+        k -= nums.shift();
+    }
+    return nums.length;
+};
+```
+
+**Explain:**
+
+Sort.
+
+**Complexity:**
+
+* Time complexity : O(n * log(n)).
+* Space complexity : O(n).
+
+## Solution 2
+
+```javascript
+/**
+ * @param {number[]} arr
+ * @param {number} k
+ * @return {number}
+ */
+var findLeastNumOfUniqueInts = function(arr, k) {
+    var map = {};
+    var nums = Array(arr.length + 1).fill(0);
+    for (var i = 0; i < arr.length; i++) {
+        if (map[arr[i]] === undefined) {
+            map[arr[i]] = 1;
+        } else {
+            nums[map[arr[i]]] -= 1;
+            map[arr[i]] += 1;
+        }
+        nums[map[arr[i]]] += 1;
+    }
+    var num = 0;
+    for (var j = 0; j < nums.length; j++) {
+        if (k > 0) {
+            var tmp = nums[j];
+            nums[j] = Math.max(0, nums[j] - Math.floor(k / j));
+            k -= tmp * j;
+        }
+        num += nums[j];
+    }
+    return num;
+};
+```
+
+**Explain:**
+
+Counting sort.
+
+**Complexity:**
+
+* Time complexity : O(n).
+* Space complexity : O(n).
+
