接外包,有相关需求的可以联系我:Telegram | Email

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

该文章创建(更新)于09/11/2020,请注意文章的时效性!

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:

    keyvalue(数量)
    12
    21
    33
    41

unique = 4

  • step3:
    keyvalue(数量)
    21
    41
    12
    33
  • step4:

    keyvalue(数量)
    21
    41
    12
    33

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

keyvalue(数量)
11
33

具体算法

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

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

参考


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2020/09/11/least-number-of-unique-integers-after-k-removals-medium/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

优惠码

阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)