Estaba tratando de resolver un problema de HackerRank en Java Deque. Mi código pasó todos los casos excepto los que tienen 100.000 entradas.
Problema: En este problema, te dan N enteros. Necesita encontrar el número máximo de enteros únicos entre todos los subarreglos contiguos posibles de tamaño M. --->Así que nos dieron N enteros, y necesitamos encontrar el número de "enteros únicos" en cada subarreglo contagioso (de tamaño M ). Y luego imprima el número máximo de esos "enteros únicos".
link: https://www.hackerrank.com/challenges/java-dequeue/problemMi código:
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); }Por favor, dime dónde salió mal mi código.
¿Cuál es el punto de esta línea?
set.add((Integer)deque.peek());No veo nada en tu código que sea lento. Solo me pregunto cómo puede realizar un seguimiento de números únicos mediante el uso de un conjunto, dado que un conjunto solo le dice si existe tal número (pero no cuántas ocurrencias hay del mismo número). Y no desea seguir escaneando el deque para ver si el número que se elimina es el último.
No creo que este sea un código excelente/rápido, pero parece pasar los casos de prueba. Llevo la cuenta de cuántos de cada entero hay en la ventana usando un mapa (y uso algo de su código).
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); } }Podemos optimizar un poco el espacio evitando el hashmap por completo, pero parece que a Hackerrank no le importa eso. De todos modos, estoy poniendo mi solución aquí que puede resolver este problema usando un mapa.
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; }Solo quería compartir cómo lo resolví en caso de que ayude.
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); }