滑動窗口應用: 成功組隊的數目 Count Number of Teams_Leetcode #1395

Ben Hershey on Unsplash

題目敘述 Count Number of Teams

給定一個輸入陣列rating，裡面代表每位成員的評分

挑選三位成員，對應到三個index i, j, k 且 i < j < k

如果rating[i] < rating[j] < rating[k] ，則此三人可以組成一隊。

或者rating[i] > rating[j] > rating[k] ，則此三人也可以組成一隊。

請問成功組成三人小隊的方法數有多少?

測試範例

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: 
成功的組隊方式 (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation:
無解 無法找到 評分遞減或評分遞增的三人組隊方式​

Example 3:

Input: rating = [1,2,3,4]
Output: 4
成功的組隊方式 (1,2,3), (1,2,4), (1,3,4), (2,3,4).

演算法 滑動窗口 + 統計左側右側資訊

假想中央那名成員為在index j 的位置，
統計左方rating 比較小 和 右方rating比較大的成員數量。

如次一來，
遞增排列組隊方法數 = 左方rating比較小的成員數量 * 右方rating比較大的成員數量

遞減排列組隊方法數 = 左方rating比較大的成員數量 * 右方rating比較小的成員數量

最後，用一個for loop，把index j 從頭到尾掃描一遍，累加所有合法的組隊方式即可。

示意圖 滑動窗口 + 統計左側右側資訊

程式碼 滑動窗口 + 統計左側右側資訊

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        r, size = rating, len( rating )
        
					# compute statistics of sliding range
        left_smaller = [ sum( r[i] < r[j] for i in range(0,j) ) for j in range(size) ]
        right_bigger = [ sum( r[j] < r[k] for k in range(j+1, size) ) for j in range(size)]
        
        num_of_teams = 0
		
					# j slides from 0 to ( n-1 ), and j stands for the index of middle element
        for j in range( 0, size):
		
            num_of_ascending_team = left_smaller[j] * right_bigger[j]
            num_of_descending_team = ( j - left_smaller[j] ) * ( size-1 - j - right_bigger[j] )
            
            num_of_teams += ( num_of_ascending_team + num_of_descending_team )
            
        return num_of_teams

複雜度分析

時間複雜度: O(n^2)

預先統計左右兩次資訊，雙層迴圈耗費O(n^2)

累加組隊數量，單層迴圈耗費O(n)

空間複雜度: O(n)

預先統計左右兩次資訊，需要額外的O(n)空間

Reference

[1] Count Number of Teams - LeetCode