Tengo una matriz de números arr y otro número K , encuentro todos los subarreglos posibles, obtengo el máximo y el mínimo en ese subarreglo y verifico si la diferencia (max - min) <= K . Encuentre cuántos de estos subarreglos existen.
Array = [1,3,6], K = 3 Los subconjuntos son: [start_index, end_index]
[0,0] subarray = [1], max - min = 1-1=0 < K [0,1] subarray = [1,3], max - min = 3 - 1 < K [0,2] subarray = [1,6], max - min = 6-1 > K [1,1] subarray = [3], max -min = 3-3 = 0 < K [1,2] subarray = [3,6], max - min = 6-3 = 3<=K [2,2] subarray = [6], max - min = 6 - 6 = 0 < k So total 5 valid sub arrays are possible with max - min <= KEste es el código que probé.
public static long process(List<Integer> list, int k) { long result = 0; for (int i = 0; i < n; i++) { int max = list.get(i), min = list.get(i); for (int j = i; j < n; j++) { int p = list.get(j); max = Math.max(max, p); min = Math.min(min, p); if(max - min <=K) result++; } } return result; }¿Quiero reducir la complejidad temporal de este algoritmo?
¿Cuál puede ser un mejor enfoque para resolver esta tarea?
Aquí hay un algoritmo de tiempo lineal.
Primero observe que, para i fijo, cuando j aumenta, max - min no puede disminuir. Si supera a K , podemos salir antes del ciclo interno. Además, podemos hacer el lazo exterior hacia abajo si queremos.
public static long process(List<Integer> list, int K) { long result = 0; for (int i = n - 1; i > -1; i--) { int max = list.get(i), min = list.get(i); int j; for (j = i; j < n; j++) { int p = list.get(j); max = Math.max(max, p); min = Math.min(min, p); if (max - min > K) break; } result += j - i; } return result; }Estos cambios nos permiten lograr un tiempo de ejecución sensible a la salida de O(n + respuesta), pero, por supuesto, la respuesta aún puede ser cuadrática.
La idea final, que nos lleva a O(n), es que, a medida que i disminuye, la j en la que sale el bucle interno no puede aumentar. Si pudiéramos iterar j hacia abajo en lugar de hacia arriba, entonces cada bucle subsiguiente podría continuar donde se detuvo el anterior. Esto requiere soporte de estructura de datos: una cola que admita push/pop/min/max cada uno en tiempo constante amortizado .
El algoritmo general itera hacia abajo sobre i . En cada iteración, empuja el elemento en el índice i a la cola; luego, hasta que la cola tenga max - min <= K , sale de la cola y finaliza la iteración agregando el número de subarreglos que comienzan en i (= la longitud de la cola).
La siguiente solución utiliza la API de flujos de Java 8, no estoy seguro de si eso ayuda en su contexto.
public static long process(List<Integer> list, int k) { return IntStream.range(0,list.size()).boxed() .flatMap(index -> IntStream.range(0,list.size()) .mapToObj(innerIndex -> new Entry(index, innerIndex))) .distinct() .filter(entry -> eligibleEntry(entry, list, k)) .count(); } private static boolean eligibleEntry(Entry entry, List<Integer> list, int k) { int start = entry.startIndex < entry.endIndex ? entry.startIndex : entry.endIndex; int end = entry.startIndex < entry.endIndex ? entry.endIndex : entry.startIndex; IntSummaryStatistics stats = IntStream.range(start, end + 1).mapToObj(list::get).collect(Collectors.summarizingInt(Integer::intValue)); return (stats.getMax() - stats.getMin()) <= k; } private static class Entry { Integer startIndex; Integer endIndex; public Entry(Integer startIndex, Integer endIndex) { this.startIndex = startIndex; this.endIndex = endIndex; } @Override public boolean equals(Object other) { if (this == other) return true; if (other == null || getClass() != other.getClass()) return false; Entry entry = (Entry) other; return (startIndex.equals(entry.startIndex) && endIndex.equals(entry.endIndex)) || (startIndex.equals(entry.endIndex) && endIndex.equals(entry.startIndex)); } @Override public int hashCode() { return Objects.hash(startIndex + endIndex); } @Override public String toString() { return "{" + startIndex + ", " + endIndex + "}"; } }Puedo esbozar una respuesta en Python que se comporte como O(n) hasta 5 lakh (2**19) ya sea que haya muchos elementos repetidos en la matriz o no. Basé esto en la observación de que el tiempo necesario para ejecutar cada una matriz sucesivamente más grande toma aproximadamente el doble de tiempo.
Suponiendo que hay repeticiones en la matriz, tiene sentido almacenar los elementos ordenados únicos, v, y su cuenta, m: si hay 10 1 y 5 2, los 50 pares de 1 y 2 no necesitan procesarse más de una vez.
Ahora, comenzando en i=0 y j=1, vea si v[1] - v[0] <= K. Si es así, calcule el conteo e incremente j. Si la nueva diferencia todavía está dentro del rango, actualice el conteo de pares entre v[0] y v[2] y v[1] y v[2]. Si al incrementar j se obtiene una diferencia demasiado grande, aumente i hasta que la diferencia esté dentro del rango; si incrementar j no es válido, entonces ya está. En Python, se ve así:
def subcount(arr, K): # get unique values and their count/tally v = {} for i, j in enumerate(arr): if j not in v: v[j] = 0 v[j] += 1 v, m = zip(*[(vi, v[vi]) for vi in sorted(v)]) # initialize n = 0 i = 0 j = 1 N = len(v) while i < N: vi = v[i] while True: if j < N and v[j] - vi <= K: # count new valid pairs for _ in range(i, j): n += m[_]*m[j] j += 1 else: if j >= N: i = j break # done while v[j] - v[i] > K: # move i to give valid diff i += 1 break # self and singleton counts for i in range(N): # self pairs n += m[i]*(m[i] - 1)//2 if v[i] <= K: # self singletons n += m[i] return n >>> a = [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20] >>> subcount(a, 4) 2022 >>> subcount(a[:20]+a[-20:],4) # first and last row of a as shown above 400Esta es una implementación de O(n) Java de la idea de David Eisenstat en otra respuesta. La estructura de datos QueueWithMinMax que uso está tomada de la estructura de datos QueueWithMax de Shivam en esta publicación , excepto que también agregué funcionalidad para rastrear mínimos.
Aquí está el programa completo (estoy iterando aumentando i en lugar de la disminución i sugerida originalmente, pero esto no tiene ninguna consecuencia).
public static long process(List<Integer> list, int k) { long result = 0; var min_max_queue = new QueueWithMinMax<Integer>(); for (int i = 0; i < list.size(); i++) { int x = list.get(i); min_max_queue.offer(x); while (min_max_queue.getMax() - min_max_queue.getMin() > k) min_max_queue.poll(); result += min_max_queue.size(); } return result; La clase QueueWithMinMax :
public class QueueWithMinMax<T extends Comparable<T>> { Queue<T> queue; Deque<T> cMax; // candidates for Max value Deque<T> cMin; // candidates for Min value public QueueWithMinMax() { queue = new LinkedList<>(); cMax = new LinkedList<>(); cMin = new LinkedList<>(); } public void offer(T element) { queue.offer(element); while (!cMax.isEmpty() && element.compareTo(cMax.peekLast()) > 0) { cMax.pollLast(); } while (!cMin.isEmpty() && element.compareTo(cMin.peekLast()) < 0) { cMin.pollLast(); } cMax.offerLast(element); cMin.offerLast(element); } public T poll() { if (cMax.peekFirst().equals(queue.peek())) cMax.pollFirst(); if (cMin.peekFirst().equals(queue.peek())) cMin.pollFirst(); return queue.poll(); } public T getMax() { return cMax.peekFirst(); } public T getMin() { return cMin.peekFirst(); } public int size() { return queue.size(); } }Ejemplo de uso:
System.out.println(process(Arrays.asList(1, 3, 6), 3)); // 5 System.out.println(process(Arrays.asList(16, 5, 10, 14), 5)); // 6 System.out.println(process(Arrays.asList(19, 3, 13, 4, 7, 3, 18), 7)); // 10