Home 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.

白話文運動

給定一個二維矩陣,矩陣內的每個元素皆由一維陣列組成: 攻擊 and 防禦

所謂弱元素,意思是其攻擊與防禦值都比某個元素還要

請回傳弱元素的數量。

題目限制

  • 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

討論區

與上述想法一致。

This post is licensed under CC BY 4.0 by the author.