我试图解决 Java Deque 上的 HackerRank 问题。我的代码通过了除了有 100,000 个输入的情况之外的所有情况。
问题：在这个问题中，给你 N 个整数。您需要在所有可能的大小为 M 的连续子数组中找到唯一整数的最大数量。 --->所以我们给定了 N 个整数，并且需要找到每个传染子数组（大小为 M）中“唯一整数”的数量。然后打印这些“唯一整数”的最大数量。
link: https://www.hackerrank.com/challenges/java-dequeue/problem
我的代码：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque deque = new ArrayDeque<>();
HashSet<Integer> set = new HashSet<>();
int n = in.nextInt();
int m = in.nextInt();
int max=0;
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.add(num);
set.add(num);
if(i>=m-1){
if(set.size()>max)max=set.size();
Integer removed=(Integer)deque.removeFirst();
set.remove(removed);
set.add((Integer)deque.peek());
}
}
System.out.println(max);
}
请告诉我我的代码哪里出了问题。
这条线的重点是什么？
set.add((Integer)deque.peek());
我没有看到你的代码中有任何慢的地方。我只是想知道如何使用集合来跟踪唯一数字，因为集合仅告诉您是否存在这样的数字（但不告诉您相同数字出现了多少次）。并且您不想继续扫描双端队列以查看被删除的数字是否是最后一个。
我不认为这是伟大/快速的代码，但它似乎通过了测试用例。我使用地图（并使用您的一些代码）来计算窗口中每个整数的数量。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque<Integer> deque = new ArrayDeque<>();
HashMap<Integer, Integer> counts = new HashMap<>();
int n = in.nextInt();
int m = in.nextInt();
int max = 0;
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.add(num);
int count = counts.getOrDefault(num, 0);
counts.put(num, ++count);
if (i >= m - 1) {
if (counts.size() > max) max = counts.size();
Integer removed = deque.removeFirst();
int removing = counts.get(removed);
removing--;
if (removing == 0) {
counts.remove(removed);
} else {
counts.put(removed, removing);
}
}
}
System.out.println(max);
}
}
只是想分享我如何解决它，以防有帮助。
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque deque = new ArrayDeque();
Set<Integer> integers = new HashSet<>();
int n = in.nextInt();
int m = in.nextInt();
long result = 0;
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.add(num);
integers.add(num);
if (deque.size() == m) {
long currentSize = integers.size();
if (currentSize > result) {
result = currentSize;
}
Integer removed = (Integer) deque.pollFirst();
if (!deque.contains(removed)) {
integers.remove(removed);
}
}
}
System.out.println(result);
}
我们可以通过避免使用 hashmap 来稍微优化空间，但 Hackerrank 似乎并不关心这一点。无论如何，我将我的解决方案放在这里，可以通过使用地图来解决这个问题。
private int countUniqueNumsInSubarrays(int[] nums, int m) {
Deque<Integer> deque = new LinkedList<>();
int maxUniqueCount = 0;
for (int i = 0; i < nums.length; i++) {
// if deque's left entry is outside the window then pop it out
while (!deque.isEmpty() && i - deque.peekFirst() >= m) {
deque.removeFirst();
}
// this will make sure that the deque only contains unique numbers,
// this is essentially helps us avoid that extra hash map
while (!deque.isEmpty() && nums[deque.peekLast()] == nums[i]) {
deque.removeLast();
}
deque.addLast(i);
if (i >= m - 1) {
maxUniqueCount = Math.max(maxUniqueCount, deque.size());
}
}
return maxUniqueCount;
}
import java.io.*;
导入java.util.*； 导入 java.util.stream.Stream;
公开课解决方案{
public static void main(String[] args) {
var sc = new Scanner(System.in);
var split = sc.nextLine().split(" ");
int n = Integer.parseInt(split[0]);
int m = Integer.parseInt(split[1]);
if (!(1 <= n && n <= 100_000)) {
System.exit(0);
}
if (!(1 <= m && m <= 100_000)) {
System.exit(0);
}
if (!(m <= n)) {
System.exit(0);
}
split = sc.nextLine().split(" ");
sc.close();
int maxNumUniqueInt = 0;
HashSet<Integer> dist = new HashSet<>();
Deque<Integer> deque = new ArrayDeque<>();
int[] arr = Stream.of(split).mapToInt(Integer::parseInt).toArray();
for (int i = 0; i < m; i++) {
deque.addLast(arr[i]);
dist.add(arr[i]);
}
int num = dist.size();
if (maxNumUniqueInt < num) {
maxNumUniqueInt = num;
}
for (int i = m; i < n; i++) {
deque.addLast(arr[i]);
dist.add(arr[i]);
int remove = deque.removeFirst();
if (!deque.contains(remove)) {
dist.remove(remove);
}
num = dist.size();
if (maxNumUniqueInt < num) {
maxNumUniqueInt = num;
}
// System.out.println(i + " | " + deque + " | " + dist + " | " + maxNumUniqueInt);
}
System.out.println(maxNumUniqueInt);
}
}
import java.util.*;
public class test {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque<Integer> deque = new ArrayDeque<>();
int n = in.nextInt();
int m = in.nextInt();
int maxUnique = 0;
Map<Integer, Boolean> uniqSet = new HashMap<>();
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.addLast(num);
uniqSet.put(num, true);
if(deque.size() == m){
// int uniqueSize = new HashSet<>(deque).size();
int uniqueSize = uniqSet.size();
maxUnique = Math.max(maxUnique, uniqueSize);
int x = deque.removeFirst();
if(!deque.contains(x)){
uniqSet.remove(x);
}
}
}
in.close();
System.out.println(maxUnique);
}
}
我们不会尝试从 hashSet 中删除元素，而是只从 deque 中删除不再位于窗口中的元素。如果一个元素不存在于双端队列中，则意味着它不再在窗口内，因此我们将其从 hashSet 中删除。
我们检查 hashSet.size() 是否大于 max 以更新唯一元素的最大计数。
public class test {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque deque = new ArrayDeque<Integer>();
HashSet hashSet = new HashSet<Integer>();
int n = in.nextInt();
int m = in.nextInt();
int max = 1;
for (int i = 0; i < n; i++) {
int num = in.nextInt();
deque.add(num);
hashSet.add(num);
if (i >= m-1) {
if (hashSet.size() > max) max = hashSet.size();
int removeElement = (Integer)deque.remove();
if (!deque.contains(removeElement)) {
hashSet.remove(removeElement);
}
}
}
System.out.println(max);
}
}