Supongo que la consulta solo tiene valores distintos.
Creo que se puede resolver en [matemáticas] O (n log {k}) [/ matemáticas]. La complejidad del espacio será [matemática] O (k) [/ matemática] si los elementos en la matriz están delimitados (menos de MAXINT – len (consulta)), o podemos modificarlos. De lo contrario, la complejidad del espacio será [matemática] O (n + k) [/ matemática].
Si [math] k << n [/ math], es básicamente un algoritmo [math] O (n) [/ math] que usa espacio constante.
Permítanme primero explicar la idea.
Estoy usando el ejemplo de John Kurlak. Suponer que:
matriz de entrada = [matemática] [1, 43, 4, 23, 1, 3, 5, 9, 1, 12, 4, 3, 4] [/ matemática]
matriz de consulta = [matemáticas] [1, 4, 3] [/ matemáticas]
- [matemática] O (k log {k}) [/ matemática] – Primero cree una matriz ordenada de elementos de consulta junto con sus índices: sorted_query = [matemática] [(1,0), (3,2), (4, 1)] [/ matemáticas]
- [matemática] O (n log {k}) [/ matemática] – Luego itere sobre la matriz de entrada y reemplace los valores con sus índices en la cola utilizando la matriz de consulta ordenada: matriz = [matemática] [0, -1, 1, -1, 0, 2, -1, -1, 0, -1, 1, 2, 1] [/ matemáticas]
- [matemáticas] O (n) [/ matemáticas] Ahora cree dos punteros de barrido, bajo y alto, que solo se mueven de izquierda a derecha. También necesita una tabla hash de frecuencia que almacene la frecuencia de cada elemento de consulta en el rango [bajo, alto] (también puede usar una matriz ordenada para actualizar las frecuencias y la complejidad se convierte en [matemáticas] O (n log {k}) [/ matemática] pero el peor de los casos está limitado). Puede aumentar las frecuencias cuando se mueve alto y disminuirlas cuando se mueve bajo. Siempre está buscando el número más pequeño con una frecuencia de 0 a la derecha de “alto”. Por ejemplo, cuando [low, high] = [math] [0, 2] [/ math] las frecuencias son [math] {0: 1, 1: 0, 2: 0} [/ math] y estamos buscando. Cuando [low, high] = [math] [8, 11] [/ math] las frecuencias deben ser [math] {0: 1, 1: 1, 2: 1} [/ math] y tenemos un rango. En realidad, la frecuencia del primer y último elemento no es importante. Además, tenga en cuenta que puede aumentar la frecuencia de un elemento, solo cuando su frecuencia es menor que la frecuencia de su predecesor. Por ejemplo, si la frecuencia de 1 y 2 son ambas 1, no debe incrementar la frecuencia de 2 si encuentra un 2.
Dejemos demostrar el ejemplo, paso a paso:
PASO 1:
consulta = [(1,0), (3,2), (4,1)]
matriz = [0, -1, 1, -1, 0, 2, -1, -1, 0, -1, 1, 2, 1]
freq = {0: 0, 1: 0, 2: 0}
bajo = 0
alto = 0
index_to_find = 0
PASO 2:
array [low] está en 0 y array [high] == index_to_find
Por lo tanto, establecemos index_to_find en 1 porque necesitamos buscar un 1 ahora.
PASO 3:
¡array [alto] no es 1! Ahora actualizamos el mapa de frecuencia {0: 1, 1: 0, 2: 0}.
Incrementamos alto a 1. array [alto] no a 1, y es un número negativo, por lo que no actualizamos la frecuencia.
Incrementamos alto nuevamente a 2. array [alto] a 1! Ahora actualizamos index_to_update a 2.
PASO 4:
array [high] no es 2. Por lo tanto, actualizamos el mapa de frecuencia {0: 1, 1: 1, 2: 0} e incrementamos high a 3.
Continuamos así hasta que high sea 5. Para entonces, el mapa de frecuencia debería verse como {0: 2, 1: 1 :, 2: 0}. Ahora tenemos un rango y lo almacenamos como el rango mínimo.
PASO 5:
Ahora queremos incrementar bajo para encontrar un nuevo rango. Pero antes de eso necesitamos actualizar el mapa de frecuencia y disminuir el valor para 0: el mapa de frecuencia se convierte en {0: 1, 1: 1, 2: 0}.
low no está en un 0, por lo que incrementamos eso hasta que la izquierda se convierte en 5. Mean mientras el mapa de frecuencia se actualiza a {0: 1, 1: 0, 2: 0}, y estamos buscando un 1.
Entonces, en general, en cada paso estamos realizando operaciones constantes y debido a que los valores bajos y altos solo se incrementan, tendremos operaciones [matemáticas] O (n) [/ matemáticas]. Si el mapa de frecuencia es un árbol binario o una matriz ordenada, la complejidad de cada paso se convierte en [matemática] O (log {k}) [/ matemática].
AHORA que desea que la matriz tenga sus valores originales después de este algoritmo, debemos asumir un límite para los valores de la matriz de entrada. Si todos los elementos de la matriz son inferiores a [MAXINT – len (consulta)], aún podemos mantener todo en su lugar:
Si un elemento es negativo, no lo tocamos.
Si 0 <= e De lo contrario, almacenamos e + len (consulta).
Una vez que hayamos terminado, simplemente podemos actualizar la matriz de entrada a sus valores originales en [math] O (n) [/ math].
Este es un código C ++ 11 para esto:
#include #include #include using std::lower_bound; using std::max; using std::min; using std::pair; using std::sort; using std::vector; using std::unordered_map; pair find_query(vector& array, const vector& query) { // We need to create a sorted query array along with their original indexes. vector> sorted_query; for (int i = 0; i < query.size(); i++) { // O(k) sorted_query.push_back({query[i], i}); } std::sort(sorted_query.begin(), sorted_query.end()); // O(k log(k)) // Better wrapping in Quora. 🙂 auto sqb = sorted_query.begin(); auto sqe = sorted_query.end(); // We need a list representing indexes of elements in array in query. // If array = [2, 1, 6, 3] and query is [1, 3], we want something like: // [-1, 0, -1, 1] // // If we assume that elements in array are bounded by "MAXINT - len(query)", // we can save a space of O(n). To that end, we modify the array in place, so // that a number less than query.size() is an index in the query, and // larger numbers are the original value + query.size() and negative numbers // have their own original value. // // If array = [2, 1, -6, 3] and query is [1, 3], we want something like: // [4, 0, -6, 1] for (auto& e : array) { // O(n log(k)) // Binary search for each element to find its index in the query. pair p = {e, 0}; auto l = std::lower_bound(sqb, sqe, p); if (l == sqe || e != l->first) { if (e >= 0) { e += query.size(); } } else { e = l->second; } } // Frequency of indexes (not the array values) in [low, high]. // If you use a tree map instead, the order of the following loop will be // O(n log(k)), but the space is guaranteed to be O(k). unordered_map freq; // Now we get two sweeping pointers to find the range [low, high] auto low = array.begin(); auto high = array.begin(); auto index_to_find = 0; pair min_range = {0, array.size()}; // We sweep from low to high. Both high and low only move towards high. while (low != array.end()) { // O(n) (NOTE the comments for freq) if (*low != 0) { if (0 <= *low && *low < query.size()) { freq[*low] = max(0, freq[*low] - 1); if (freq[*low] == 0) { index_to_find = min(index_to_find, *low); } } low++; if (high < low) { // low passed high, so we need to reset high and index_to_find. high = low; index_to_find = 0; } continue; } while (index_to_find != query.size() && high != array.end()) { while (*high != index_to_find) { if (0 <= *high && *high < query.size()) { if (*high == 0 || freq[*high] < freq[*high - 1] ) { freq[*high]++; } } high++; } index_to_find++; } if (high == array.end()) { break; } // We found a new range. if (high - low < min_range.second - min_range.first) { min_range = {low - array.begin(), high - array.begin()}; } low++; } // Transform array to its original values. for (auto& e : array) { if (e < 0) { continue; } if (e >= query.size()) { e -= query.size(); continue; } e = query[e]; } return min_range; } int main() { vector array{ 1, 43, 4, 23, 1, 3, 5, 9, 1, 12, 4, 3, 4 }; vector query{ 1, 4, 3 }; vector c = array; auto r = find_query(array, query); printf("Min range is [%d,%d]\n", r.first, r.second); return 0; }