# 1996.游戏中弱角色的数量

## 问题描述
[1996. 游戏中弱角色的数量 (Medium)](https://leetcode.cn/problems/the-number-of-weak-characters-in-the-game/)

你正在参加一个多角色游戏，每个角色都有两个主要属性： **攻击** 和 **防御** 。给你一个二维整数数组
`properties` ，其中 `properties[i] = [attackᵢ, defenseᵢ]`
表示游戏中第 `i` 个角色的属性。
如果存在一个其他角色的攻击和防御等级 **都严格高于** 该角色的攻击和防御等级，则认为该角色为 **弱角色**
。更正式地，如果认为角色 `i` **弱于** 存在的另一个角色 `j` ，那么 `attackⱼ > attackᵢ`
且 `defenseⱼ > defenseᵢ` 。
返回 **弱角色** 的数量。
**示例 1：**
```
输入：properties = [[5,5],[6,3],[3,6]]
输出：0
解释：不存在攻击和防御都严格高于其他角色的角色。
```
**示例 2：**
```
输入：properties = [[2,2],[3,3]]
输出：1
解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
```
**示例 3：**
```
输入：properties = [[1,5],[10,4],[4,3]]
输出：1
解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
```
**提示：**
- `2 <= properties.length <= 10⁵`
- `properties[i].length == 2`
- `1 <= attackᵢ, defenseᵢ <= 10⁵`

## 解题思路
首先将角色按照攻击值从大到小排序，至于相同攻击值之间的角色的排序，有两种思路
### 按照防御值从大到小排序
利用哈希表记录每个攻击值有多少攻击值相同的角色，遍历排好序的`properties`数组时，从`i = 1, j= roles[properties[i][0]]`开始遍历，一直到`j == i + roles[properties[i][0]]`，此时`++i; j = roles[properties[i + 1][0]]`，角色的攻击值一定是相对较小的，如果角色的防御值小于记录的防御值最大值，那么`i + roles[properties[i][0]]] - j`就是本次`i`循环中发现的弱角色的数量，否则更新防御最大值`defend_max`.

### 按照防御值从小到大排序
直接遍历排好序的`properties`数组，如果`properties[i][0] < properties[0][0] && properties[i][1] < defend_max`, `res++`；如果`properties[i][1] > defend_max`，更新`defend_max`.

## 代码
### 按照防御值从大到小排序
```cpp
class Solution {
  public:
    int numberOfWeakCharacters(vector<vector<int>> &properties) {
        std::sort(properties.begin(), properties.end(), [&](vector<int> &vec1, vector<int> &vec2) {
            if (vec1[0] == vec2[0])
                return vec1[1] >= vec2[1];
            return vec1[0] > vec2[0];
        });
        int cnt = 0;
        int attack_max = properties[0][0];
        int defend_max = properties[0][1];
        unordered_map<int, int> roles; // 记录同一攻击值有多少角色
        for (int i = 0; i < properties.size(); i++) {
            roles[properties[i][0]]++;
        }
        for (int i = roles[attack_max]; i < properties.size(); i += roles[properties[i][0]]) {
            int j = i;
            while (j < i + roles[properties[i][0]] && properties[j][1] >= defend_max) {
                j++; // 寻找小于defend_max的properties[j][1]
            }
            cnt += i + roles[properties[i][0]] - j;
            defend_max = std::max(defend_max, properties[i][1]); // 更新defend_max
        }
        return cnt;
    }
};
```

### 按照防御值从小到大排序
```cpp
class Solution {
  public:
    int numberOfWeakCharacters(vector<vector<int>> &properties) {
        std::sort(properties.begin(), properties.end(), [&](vector<int> &vec1, vector<int> &vec2) {
            if (vec1[0] == vec2[0])
                return vec1[1] <= vec2[1];
            return vec1[0] > vec2[0];
        });
        int cnt = 0;
        int attack_max = properties[0][0];
        int defend_max = properties[0][1];
        for (int i = 1; i < properties.size(); i++) {
            if (properties[i][0] < attack_max && properties[i][1] < defend_max) {
                cnt++;
            } else if (properties[i][1] > defend_max) {
                defend_max = properties[i][1];
            }
        }
        return cnt;
    }
};
```