最快的方法來計算獨特值的最大數量在德克

Question

我試圖找到最快的方式來計算從控制檯採取的n系列整數的m大小的子陣列中的唯一值的最大數量。有什麼辦法可以進一步優化這段代碼嗎？感謝的提前，亞歷克斯

import java.util.*; 
public class test { 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     Deque deque = new ArrayDeque<>(); 
     int n = in.nextInt(); 
     int m = in.nextInt(); 
     long count = 0, c = 0; 

     for (int i = 0; i < m; i++) deque.addFirst(in.nextInt()); 
     count = deque.stream().distinct().count(); 
     for (int i = 0; i < n - m; i++) { 
      count = Math.max(count, deque.stream().distinct().count()); 

      deque.removeLast(); 
      deque.addFirst(in.nextInt()); 
     } 
     System.out.println(count); 
    } 
} 

Answer 1

這O（NM）（假設distinct是O（M））。通過跟蹤窗口內當前非零計數值的數量，應該可以在O（N）中執行此操作。

僞代碼：

for (int i = M; i < N; i++) { 
    counts[x[i-M]]--; 
    if (counts[x[i-M]] == 0) { 
     nonzero--; 
    } 

    if (counts[x[i]] == 0) { 
     nonzero++; 
    } 
    counts[x[i]]++; 

    maxNonzero = max(maxNonzero, nonzero); 
}