1996. The Number of Weak Characters in the Game
Post
Cancel

# 1996. The Number of Weak Characters in the Game

Leetcode #1996

## 題目描述

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense.

You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels.

More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

### 題目限制

• 2 <= properties.length <= 105
• properties[i].length == 2
• 1 <= attacki, defensei <= 105

## 具體測資

### Case 1

1 2 3 Input : properties = [[5,5],[6,3],[3,6]] Output : 0 Explanation: No character has strictly greater attack and defense than the other. 

### Case 2

1 2 3 Input : properties = [[2,2],[3,3]] Output : 1 Explanation: The first character is weak because the second character has a strictly greater attack and defense. 

### Case 3

1 2 3 Input : properties = [[1,5],[10,4],[4,3]] Output : 1 Explanation: The third character is weak because the second character has a strictly greater attack and defense. 

### Case 4

1 2 Input : properties = [[5,5],[6,7],[5,6],[3,8],[3,4],[2,2]] Output : 4 

## 解題想法

### 概念

#### 暴力法

1. 遍歷整個二維矩陣，進行兩兩比對。

#### 快速解決法

1. 排序

確保二為矩陣的順序，攻擊值由大至小遞減排列、防禦值由小至大遞增排列。

1 2 properties = [[5,5],[6,7],[5,6],[3,8],[3,4],[2,2]] sorted_pro = [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] 
2. 遍歷排序的二維矩陣

遍歷時，因為攻擊值由大至小遞減排列，因此，只需判斷當前元素的防禦值是否比當前最大防禦值還要小，即可判定當前元素是否微弱元素。

若較小，則當前元素即為弱元素。

若較大，則更新最大防禦值。

舉例來說:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 sorted_pro = [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ----- curr_max_defense = 0 [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ^ ----- curr_max_defense = 7 [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ^ weak ----- curr_max_defense = 7 [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ^ weak ----- curr_max_defense = 7 [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ^ weak ----- curr_max_defense = 7 [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ^ ----- curr_max_defense = 8 [[6,7],[5,5],[5,6],[3,4],[3,8],[2,2]] ^ weak 

### Pseudo Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 GIVEN: properties is a 2D array. ## Sort by attack value descendingly and sort by defense value ascendingly sorted_properties <- Sort(properties) ## Iterate sorted_properties to count weak elements SET cuur_max_defense is 0. SET ret is 0. FOR each (attack, defense) of sorted_properties do IF d < curr_max_defense do ret <- ret + 1 ELSE curr_max_defense <- d ENDIF ENDFOR RETURN ret 

### 複雜度分析

• 時間複雜度: O(NlogN)
1. 排序的平均時間複雜度為 O(NlogN)。

2. 遍歷的時間複雜度為 O(N)。

• 空間複雜度: O(1)

## 實際解題

### Python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def numberOfWeakCharacters(self, properties: List[List[int]]) -> int: sorted_p = sorted(properties, key=lambda k: (-k[0], k[1])) ret = 0 curr_max = 0 for _, d in sorted_p: if d < curr_max: ret += 1 else: curr_max = d return ret