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（数量） 21 41 1 2 3 3
这里先把2，4删掉，但还要删一个数，默认从排序下一个（这里即为删掉一个1）开始！ 最后可得如下得map！所以最后结果为unique value = uninue - 2
| key | value（数量） |
|---|---|
| 1 | 1 |
| 3 | 3 |
具体算法
Java
未通过时间测试，最后一个数据太变态了，自己本机运行都运行不了，说数据量过大！
- 这里用到JAVA MAP，具体可参考Java 中的的 Map
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
具体过程可以参照下面的哪个Python代码！
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)))
