LeetCode 1996《游戏中弱角色的数量》O(n²)解法错误原因咨询

你的解法错误的核心原因是统计对象搞混了：题目要求统计的是「弱角色的数量」（即每个满足条件的角色i只算1次，不管有多少个j比他强），但你的代码统计的是「所有j强于i的(i,j)配对数量」——同一个弱角色i如果被多个j碾压，会被重复计数多次，这就是为什么测试用例输出会从预期的6变成26。

举个例子，测试用例里的角色[7,7]，有[9,8]、[8,10]两个角色都比他强，你的代码会给count加2，但这个角色只应该被算作1个弱角色。

修正O(n²)解法 #

要修复这个问题，只需要对每个角色i，判断是否存在至少一个j满足条件，一旦找到就标记为弱角色，不再继续统计该i的其他配对：

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int count = 0;
        int n = properties.size();
        for (int i = 0; i < n; ++i) {
            bool isWeak = false;
            for (int j = 0; j < n; ++j) {
                if (i == j) continue; // 跳过自己和自己比较
                if (properties[j][0] > properties[i][0] && properties[j][1] > properties[i][1]) {
                    isWeak = true;
                    break; // 找到一个满足条件的j就停止内层循环
                }
            }
            if (isWeak) ++count;
        }
        return count;
    }
};

这个修改后的代码会正确输出测试用例的6，因为每个弱角色只会被计数一次。

更高效的O(n log n)解法 #

不过O(n²)的解法在数据量较大时会超时，推荐用排序+贪心的优化思路：

1. 排序规则：将角色按攻击力降序排列，如果攻击力相同，则按防御力升序排列。这样保证攻击力高的角色先被遍历，且攻击力相同的角色中，防御力低的排在前面（避免误判同攻击力的角色为弱角色）。
2. 贪心遍历：维护一个max_def变量，记录遍历过的角色的最大防御力。如果当前角色的防御力小于max_def，说明存在之前的角色（攻击力严格大于当前，因为同攻击力的角色防御力更小，不会更新max_def）比他强，即当前是弱角色。

代码实现：

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        // 按攻击力降序，攻击力相同则防御力升序排序
        sort(properties.begin(), properties.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] != b[0]) return a[0] > b[0];
            return a[1] < b[1];
        });
        
        int count = 0;
        int max_def = 0;
        for (auto& p : properties) {
            if (p[1] < max_def) {
                ++count;
            } else {
                max_def = p[1];
            }
        }
        return count;
    }
};

这个解法时间复杂度主要由排序决定，为O(n log n)，能处理更大规模的输入。

内容的提问来源于stack exchange，提问作者Mukund Shukla