Java教程

TreeSet和TreeMap中“相等”元素可能并不相等

本文主要是介绍TreeSet和TreeMap中“相等”元素可能并不相等,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

TreeSet和TreeMap元素之间比较大小是借助Comparator对象的compare方法。

但有些时候,即便compare()返回0也不意味着这两个元素直观上相同。
比如元素是二元组[a,b]的形式:对于[a1,b1]和[a2,b2],规定a1>a2&&b1>b2时[a1,b1]>[a2,b2],a1<a2&&b1<b2时[a1,b1]<[a2,b2],否则[a1,b1]=[a2,b2]。
也就是说即便[a1,b1]=[a2,b2]完全可能a1!=b1,a2!=b2。特别的对于TreeSet,如果添加多个所谓的“相等”元素,那么后面的元素实际上是没有被添加进去的,因为他们被判定相等,即便他们是不同的二元组。

例题:5864.游戏中弱角色的数量

你正在参加一个多角色游戏,每个角色都有两个主要属性:攻击 和 防御 。给你一个二维整数数组 properties ,其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。

如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级,则认为该角色为 弱角色 。更正式地,如果认为角色 i 弱于 存在的另一个角色 j ,那么 attackj > attacki 且 defensej > defensei 。

返回 弱角色 的数量。

下面是错误的做法:将所有二元组添加进TreeSet,然后遍历properties数组,对于每个元素,通过higher()判断是否有比当前元素更大的元素。

   public int numberOfWeakCharacters(int[][] properties) {
        int cnt=0;
        TreeSet<int[]> set=new TreeSet<>(new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                if(a[0]>b[0]&&a[1]>b[1]) return 1;
                else if(a[0]<b[0]&&a[1]<b[1]) return -1;
                else return 0;
            }
        });
        for(int[] p:properties) set.add(p);
        for(int[] p:properties){
            if(set.higher(p)!=null) cnt++;
        }
        return cnt;
    }

比如对于输入案例properties = [[1,5],[10,4],[4,3]],实际上set中只有一个元素[1,5],因为[10,4]被判定与[1,5]相等,所以没有被添加到set,同理[4,3]也被判定与[1,5]相等,所以也没有被添加到set。


这道题正确的做法是重定义排序规则在遍历一遍properties数组即可。按攻击力降序、防守力升序的规则排序。遍历数组,记录遍历元素的最大防守值,如果不等于当前防守值,则说明前面存在元素攻击防守均强于当前元素。

   public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                if(a[0]!=b[0]){
                    return b[0]-a[0];
                }
                else{
                    return a[1]-b[1];
                }
            }
        });
        int max=0,cnt=0;
        for(int i=0;i<properties.length;++i){
            if(max<=properties[i][1]) max=properties[i][1];
            else cnt++;
        }
        return cnt;
    }
这篇关于TreeSet和TreeMap中“相等”元素可能并不相等的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!