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为止

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

这里先把2，4删掉，但还要删一个数，默认从排序下一个（这里即为删掉一个1）开始！ 最后可得如下得map！所以最后结果为unique value = uninue - 2

key	value（数量）
1	1
3	3

未通过时间测试，最后一个数据太变态了，自己本机运行都运行不了，说数据量过大！

• 这里用到JAVA MAP，具体可参考Java 中的的 Map

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;
        }
    }

具体过程可以参照下面的哪个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;

        }
    }

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 !");
        }
    }
}

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
                        }
                    }
                }
            }

看完感觉自己对数据拥有的类不太熟悉，同时自己的数据算法过于低级，过于简单而复杂。忽略了好的算法带来的好处！

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)))

• Java 中的的 Map
• https://www.cnblogs.com/lzq198754/p/5780165.html
• https://www.acwing.com/file_system/file/content/whole/index/content/596633/

要不赞赏一下?

微信

支付宝

PayPal

Bitcoin