題目描述
在電腦科學的領域,一個雙向佇列(double-ended queue, dequeue, deque)是一種佇列的抽象資料型態,雙向佇列中的每個元素都可以在佇列的最前端或最後端被新增移除。
Deque介面被許多集合類別所實作,像是LinkedList和ArrayDeque。舉例來說,雙向佇列的物件可以用以下方式宣告與實體化:
Deque deque = new LinkedList<>();
或
Deque deque = new ArrayDeque<>();
在這個題目中,您將會得到N個整數。您需要從任意大小為M的連續子陣列中找出其中最大的不同整數的數量。
原題網址
輸入格式
輸入第一行包含N和M兩個整數,分別表示整數的數量和子陣列的大小,範圍都在1到100000之間(包含1和100000),M小於等於N。接下來的一行中,包含N個用空格分隔的整數,範圍在0到10000000之間(包含1和10000000)。
輸出格式
輸出所有子陣列中,最大的不重複整數數量。
範例輸入
6 3
5 3 5 2 3 2
5 3 5 2 3 2
範例輸出
3
額外解釋
所有子陣列如下:
s1=⟨5,3,5⟩,有2個不重複的整數。
s2=⟨3,5,2⟩,有3個不重複的整數。
s3=⟨5,2,3⟩,有3個不重複的整數。
s4=⟨2,3,2⟩,有2個不重複的整數。
所以最大不重複整數數量為3。
解題概念
一邊讀入整數一邊將整數存入Dequeue中,並且使用一個HashMap
參考答案
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Scanner;
public class test {
public static void main(final String[] args) {
final Scanner in = new Scanner(System.in);
final Deque<Integer> deque = new ArrayDeque<>();
final int n = in.nextInt();
final int m = in.nextInt();
int maxUnique = 0;
int uniqueSize = 0;
final HashMap<Integer, Integer> counterMap = new HashMap<>();
for (int i = 0; i < n; ++i) {
final int num = in.nextInt();
if (deque.size() >= m) {
final Integer pollNum = deque.pollLast();
final int count = counterMap.get(pollNum);
if (count == 1) {
counterMap.remove(pollNum);
--uniqueSize;
} else {
counterMap.put(pollNum, count - 1);
}
}
deque.addFirst(num);
if (counterMap.containsKey(num)) {
counterMap.put(num, counterMap.get(num) + 1);
} else {
counterMap.put(num, 1);
++uniqueSize;
if (uniqueSize > maxUnique) {
maxUnique = uniqueSize;
}
}
}
System.out.println(maxUnique);
}
}