InterviewBit – Distinct Numbers in Window

Source: Distinct Numbers in Window

Problem Description

You are given an array of N integers, A₁, A₂ ,…, A_N and an integer B. Return the of count of distinct numbers in all windows of size B.

Formally, return an array of size N-B+1 where i’th element in this array contains number of distinct elements in sequence A_i, A_i+1 ,…, A_i+B-1.

NOTE: if B > N, return an empty array.

Input Format

First argument is an integer array A
Second argument is an integer B.

Output Format

Return an integer array.

Example Input

Input 1:

 A = [1, 2, 1, 3, 4, 3]
 B = 3

Input 2:

 A = [1, 1, 2, 2]
 B = 1

Example Output

Output 1:

 [2, 3, 3, 2]

Output 2:

 [1, 1, 1, 1]

Example Explanation

Explanation 1:

 A=[1, 2, 1, 3, 4, 3] and B = 3
 All windows of size B are
 [1, 2, 1]
 [2, 1, 3]
 [1, 3, 4]
 [3, 4, 3]
 So, we return an array [2, 3, 3, 2].

Explanation 2:

 Window size is 1, so the output array is [1, 1, 1, 1].

---

解題：

這題其實還蠻簡單的，因為是要計算 sliding window 內的個別元素計數值，在前面的解題系列就以探討過，用個 hashmap 來進行統計，並且在每次sliding的時候執行計數的加減即可。鑑於一般 dict 函式在建立 key : value 需要用不少 try / except 的條件來新增或刪除 key-value 對應，筆者這題是比較偷吃步的直接導入 collections.Counter 來進行計數。但用 collections.Counter 或計數用 hashmap 時須注意到，即使計數歸零，該組 key-value pair 還是存在於該字典內，在執行 len(dict) 時依然會將其計入，故在執行 len() 前需要先下判定式，若更新 sliding window 滑走移除的數字後會使該組計數值歸零，則應執行 dict.pop(key) 將其自字典中移除。

Code:

from collections import Counter
class Solution:
    # @param A : list of integers
    # @param B : integer
    # @return a list of integers
    def dNums(self, A, B):
        n = len(A)
        output = []
        if B > n: return output
        counter = Counter(A[:B])
        output.append(len(counter))
        for i in range(B, n):
            counter[A[i-B]] -= 1
            counter[A[i]] += 1
            if counter[A[i-B]] == 0:
                counter.pop(A[i-B])
            output.append(len(counter))
        return output

GitHub: GitHub