3318. Find X-Sum of All K-Long Subarrays I

題目

You are given an array nums of n integers and two integers k and x.

The x-sum of an array is calculated by the following procedure:

Count the occurrences of all elements in the array.
Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.
Calculate the sum of the resulting array.

Note that if an array has less than x distinct elements, its x-sum is the sum of the array.

Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

題目連結

思路

此題主要需要解決的是依照題目敘述實作出 x-sum 方法，只要將 x-sum 成功實現之後再將輸入的 nums 代入即可完成題目所求。

x-sum 所要求的規則是：

計算陣列內各個數字出現的次數
取出出現次數最多的前 x 個數字 (如果出現次數有重複的狀況，取出其中最大的數字)
將取出的數字進行加總 (需乘上出現次數)

因此理想上的作法是將輸入的陣列先進行計數，來得到一個 dict 形式的物件，在 python 中可以利用 Counter 來快速得到計數結果。取得計數結果 counter 後，由於我們需要取出出現次數最多的前兩個數字，可以利用對 counter 進行排序，再取出首或尾的兩個元素即可。

那在 python 的排序方法中，我們可以使用 sorted() 方法來處理任何可迭代的值，另外在 sorted() 方法還可以帶入 key 值來自定義排序的依據和目標，因此可以寫成：

sorted(counter.items(), key=lambda x: (x[1], x[0]))

具體上是將 counter 當中的每個 item，也就是每對 key-value 組拿出來進行排序，後面的 key 則是使用到 lambda 函式來表示，這邊 lambda x 中的 x 就是代表 counter 裡面的每個 item，它會以一個 tuple 的格式來放入 key 和 value。

而在 lambda 函式中的 (x[1], x[0]) 代表先以 x[1] (也就是 value，出現次數) 作為排序目標，當遇到相同值的時候，再根據 x[0] (key，陣列中的數字本身) 來排序，這樣我們就可以得到一個以出現次數為主，陣列數字為輔去排序得到的 tuple array，會長的像是：

[(1, 1), (4, 1), (2, 2)]

接下來再取出排序後的陣列裡後 x 項進行加總即可，因此完整的 x-sum 方法實作可以表示成：

def xSum(arr: List[int], x):
  count = Counter(arr)
  sortedCount = sorted(counter.items(), key=lambda k: (k[1], k[0]))
  candidates = sortedCount[-x:]
  
  return sum(cand[0] * cand[1] for cand in candidates)

最後根據題目的要求，輸入的 nums 總共可以進行 n-k+1 輪 x-sum 的操作，所以在這邊就以迴圈的方式來對 nums 進行切片並依序進行 x-sum 操作即可完成。

Full Code

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        l = n - k + 1
        ans = []

        def xSum(counter: Counter, x) -> int:
            sortedNums = sorted(counter.items(), key=lambda x: (x[1], x[0]))
            cands = sortedNums[-x:]
            return sum([cand[0] * cand[1] for cand in cands])

        for i in range(l):
            subNums = nums[i:i+k]
            counter = Counter(subNums)
            ans.append(xSum(counter, x))

        return ans