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中“相等”元素可能并不相等

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

最新文章

热门文章