Schnellste Methode zum Zählen der maximalen Anzahl von eindeutigen Werten in Deque

Question

Ich versuche den schnellsten Weg zu finden, um die maximale Anzahl von eindeutigen Werten in m-großen Unterfeldern einer Reihe von n ganzen Zahlen aus der Konsole zu zählen. Gibt es eine Möglichkeit, diesen Code weiter zu optimieren? Danke im Voraus, Alex

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

Dies wird O (NM) (unter der Annahme distinct ist O (M)). Es sollte möglich sein, dies in O (N) zu tun, indem die Anzahl der Werte mit Nicht-Null-Zählungen verfolgt wird, die sich gegenwärtig innerhalb des Fensters befinden.

Pseudocode:

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); 
}