LeetCode: 1481. Least Number of Unique Integers after K Removals Medium

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

# 思路

• step1:升序排序
• step2:获取每一个值(key)得数量(value)，并存到Map中（同时计算有多少个不同得unique值）
• step3:对map得value进行升序排序
• step4:k从最小数量（value）依次减去直到0为止

## eg

arr = [4,3,1,1,3,3,2],k =3

• step1:
[1,1,2,3,3,3,4]

• step2:

key value(数量)
1 2
2 1
3 3
4 1

unique = 4

• step3:
key value（数量）
2 1
4 1
1 2
3 3
• step4:

key value（数量）
2 1
4 1
1 2
3 3

key value（数量）
1 1
3 3

# 具体算法

## Java

### My Way

``````public class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Arrays.sort(arr);

Map map = new HashMap();
int the_same_number_count = 0;
int m = 0;
while(m <= arr.length - 1){
if(the_same_number_count > arr.length){
break;
}

if(m == arr.length -1){//如果只有最后一个数量了
map.put(arr[m],1);
the_same_number_count++;
break;
}else{
int n = m + 1;

if(n > arr.length){
break;
}

int count = 1;
while(n <= arr.length - 1){
if(arr[m] == arr[n]){
count++;
n++;
if(n > arr.length - 1){
the_same_number_count++;
map.put(arr[m],count);
m = m + count;
break;
}
}else{
map.put(arr[m],count);
the_same_number_count++;
m = m + count;
break;
}
}
}
}

// 通过ArrayList构造函数把map.entrySet()转换成list
List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
// 通过比较器实现比较排序
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> mapping1, Map.Entry<Integer, Integer> mapping2) {
return mapping1.getValue().compareTo(mapping2.getValue());
}
});

//最后得出k
for (Map.Entry<Integer, Integer> mapping : list) {
int i = 1;
//这里的逻辑在如果默认没有1个数的情况下有点问题
while(i <= arr.length & k >= 0){
if(mapping.getValue() == i ){
k -= i;
if(k >= 0){
the_same_number_count--;
}
}
i++;
}
}

return the_same_number_count;
}
}
``````

### Best Way

``````public class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Arrays.sort(arr);

Map map = new HashMap();
//      count the same number and form a map like(number,the count of the number)
int n = 1;  //the count of one value
for (int i = 0; i < arr.length; i++) {
if(map.containsKey(arr[i])){   //Map 中是否存在改key
n++;
map.put(arr[i], n);
}else{
map.put(arr[i],1);
n = 1;
}
}

List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());

Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> mapping1, Map.Entry<Integer, Integer> mapping2) {
return mapping1.getValue().compareTo(mapping2.getValue());
}
});

int lenght = map.size();  //获取map中的键值个数
int delete_count = 0;//要删除的键值个数

for (Map.Entry<Integer,Integer> mapping:list){
if(mapping.getValue() <= k){
k -= mapping.getValue();
delete_count += 1;
}
}

return lenght - delete_count;

}
}
``````

### test code

``````import java.util.*;

public class leetcode_one{
static class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Arrays.sort(arr);

Map map = new HashMap();
//      count the same number and form a map like(number,the count of the number)
int n = 1;  //the count of one value
for (int i = 0; i < arr.length; i++) {
if(map.containsKey(arr[i])){   //Map 中是否存在改key
n++;
map.put(arr[i], n);
}else{
map.put(arr[i],1);
n = 1;
}
}

List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
System.out.println("输出map的值");
for (Map.Entry<Integer, Integer> mapping : list) {
System.out.println(mapping.getKey() + " ：" + mapping.getValue());
}

//            List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
// 通过比较器实现比较排序
Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> mapping1, Map.Entry<Integer, Integer> mapping2) {
return mapping1.getValue().compareTo(mapping2.getValue());
}
});

for (Map.Entry<Integer,Integer> mapping:list){
System.out.println(mapping.getKey() + " => " + mapping.getValue());
}

int lenght = map.size();  //获取map中的键值个数
int delete_count = 0;//要删除的键值个数

for (Map.Entry<Integer,Integer> mapping:list){
if(mapping.getValue() <= k){
k -= mapping.getValue();
delete_count += 1
;
}
}

return lenght - delete_count;

}
}

public static void main(String[] args) {
System.out.print("hello world !");
try {
System.out.println("Start!");
Solution S = new Solution();
int m[]  = {4,3,1,1,3,3,2};
int k = 3;
//            int m[]  = {5,5,4};
//            int k = 1;
int output = S.findLeastNumOfUniqueInts(m,k);
System.out.println("OUTPUT:");
System.out.println(output);
} catch (Exception ex) {
System.out.print("Something Wrong !");
}
}
}
``````

## python3

### My Way

``````class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
#升序排序
arr.sort(reverse=False)

dict = {}

the_same_number_count = 0
m = 0
while(m <= len(arr) - 1){
if(the_same_number_count > len(arr)){
break
}

if(m == arr.length -1){
map.put(arr[m],1)
dict[arr[[m]]]  = 1
the_same_number_count++
break
}else{
n = m + 1
if(n > len(arr)){
break
}

count = 1
while(n <= len(arr) - 1){
if(arr[m] == arr[n]){
count++
n++
if(n > len(arr) - 1){
the_same_number_count++
map.put(arr[m],count)
dict[arr[m]] = count
m = m + count
break
}
}else{
dict[arr[m]] = count
the_same_number_count++
m = m + count
break
}
}
}
}
``````

### Good Way

``````class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
cnt = {}
# 统计频次
for i in arr:
if cnt.get(i) is None:
cnt[i] = 1
else:
cnt[i] += 1

s = sorted(cnt.items(), key=lambda e: e[1], reverse=False)

length = len(cnt)

res = 0
for item in s:
if item[1] <= k:
k -= item[1]
res += 1

return length - res

``````
• 测试完整代码及其注释
``````class Solution:
def findLeastNumOfUniqueInts(self, arr, k) :
cnt = {}
# 统计频次
# 把arr的值作为cnt字典中的key,把arr的个数作为cnt中的value；
#依次遍历arr，把arr的值放到cnt字典中，若cnt字典中存在arr的值，则其value（即arr值得个数）增加1,依次到最后一个则会形成arr得值及其对应个数得数据字典
for i in arr:
if cnt.get(i) is None:
cnt[i] = 1
else:
cnt[i] += 1

#利用key（arr得值）进行Sorted升序排序
#cnt.items()返回可遍历的(键, 值) 元组数组。
#lambda 匿名函数??貌似是sorted 得具体用法，这里指用key 进行排序???
#当待排序列表的元素由多字段构成时，我们可以通过sorted(iterable，key，reverse)的参数key来制定我们根据那个字段对列表元素进行排序。
#key=lambda 元素: 元素[字段索引]
#例如：想对元素第二个字段排序，则
#key=lambda y: y[1] 备注：这里y可以是任意字母，等同key=lambda x: x[1]
s = sorted(cnt.items(), key=lambda e: e[1], reverse=False)
print(s)  # 得到得的结果貌似可以称作一个嵌套列表???

length = len(cnt)
print('\nlength of s :' + str(length))

res = 0
for item in s:
print(item)
if item[1] <= k:   # 从最小值依次减去的个数
k -= item[1]
res += 1       # 剔除掉的unique值得个数

return length - res    # 剩余未剔除得unique值得个数

arr_item = [4,3,1,1,3,3,2]
k = 3
S = Solution()
print('\nResult:' + str(S.findLeastNumOfUniqueInts(arr_item,k)))
``````

# 参考

### 要不赞赏一下?

 微信 支付宝 PayPal Bitcoin

``https://www.emperinter.info/2020/09/11/least-number-of-unique-integers-after-k-removals-medium/``

## 优惠码

 阿里云国际版 20美元 Vultr 10美元 搬瓦工 | Bandwagon 应该有折扣吧？ Just My Socks JMS9272283 【注意手动复制去跳转】 域名 | namesilo `emperinter`(1美元) 币安 币安