Leetcode-1996游戏中的弱字符数

Question

问题:您正在玩一个包含多个字符的游戏，每个角色都有两个主要属性:攻击和防御。您将获得一个2D整数数组属性，其中properties the = attacki，defensei表示游戏中ith字符的属性。

如果任何其他角色的攻击和防御等级都严格大于该角色的攻击和防御级别，则称该角色为弱角色。更正式地说，如果存在另一个字符j，其中attackj > attacki和defensej > defensei，则称为弱字符。

返回弱字符数。

我的解决方案：

class Solution {
public:
    
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int count =0;
        for(int i=0; i<properties.size(); i++){
            for(int j=0; j<properties.size(); j++){
                if((properties[j][0]>properties[i][0])&& (properties[j][1]>properties[i][1])){
                    count++;
                }
            }
        }
        return count;
    }
};

这是我的解决方案。我不知道为什么这不管用。我基本上比较了每个人在O(n^2)方式和增量计数，如果发现这样的情况。

测试案例：[7，7，1，2，9，7，7，3，3，10，9，8，8，10，4，3，3，1，5，5]

我的产出: 26预期:6

Answer 1

问题是，您的算法是计算所有的对，其中一个比另一个“弱”，但这不是什么问题。您应该计算所有弱于的条目(而不是对)，至少还要计算另一个。不要在计算中包括你发现同一个项目被证明更弱的次数。只需计算一个事实，即它比弱一些其他条目。

Answer 2

正如前面提到的--您的问题是，您没有计算弱字符的数量，而是有多少个字符更强，也就是说，每个弱字符要多次增加变量count，最简单的解决方法是在找到一个更强的字符时立即停止计算：

class Solution {
public:
    
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int count =0;
        for(int i=0; i<properties.size(); i++){
            for(int j=0; j<properties.size(); j++){
                if ((properties[j][0] > properties[i][0]) && (properties[j][1] > properties[i][1])) {
                    count++;
                    break; // <-- HERE we need to stop
                }
            }
        }
        return count;
    }
};

这段代码应该通过所有的测试，但是它会因为超时而失败。

要真正解决问题--您需要改变解决问题的方法，我不打算发布完全有效的解决方案，但是有一些提示：

如果对输入数组进行排序，

1. 怎么办？因此，您将知道，在攻击能力方面，过去的所有字符都是>=。那么，如何减少比较的数量呢？
2. ，如果在当前攻击/防御之外，您也知道当前项目之后的最大防御能力呢？