superponer - ¿Cómo puedo encontrar un número que ocurre un número impar de veces en una matriz clasificada en tiempo O(n)?
superponer graficas en r (15)
Tengo una pregunta y traté de pensar una y otra vez ... pero no conseguí nada, por lo que publiqué la pregunta aquí. Tal vez podría obtener un punto de vista de los demás, para tratar de hacerlo funcionar ...
La pregunta es: se nos da una matriz CLASIFICADA, que consiste en una colección de valores que se repiten UNA cantidad de veces, excepto uno, que ocurre una cantidad IMPAR de veces. Necesitamos encontrar la solución en tiempo log n.
Es fácil encontrar la solución en el tiempo O (n), pero parece bastante complicado de realizar en tiempo de registro n.
AHhh. Hay una respuesta
Haga una búsqueda binaria y, mientras busca, para cada valor, retroceda hasta encontrar la primera entrada con ese mismo valor. Si su índice es par, es antes del bicho raro, así que muévase hacia la derecha.
Si su índice de matriz es impar, es después del oddball, por lo tanto, muévase hacia la izquierda.
En pseudocódigo (esta es la idea general, no probada ...):
private static int FindOddBall(int[] ary)
{
int l = 0,
r = ary.Length - 1;
int n = (l+r)/2;
while (r > l+2)
{
n = (l + r) / 2;
while (ary[n] == ary[n-1])
n = FindBreakIndex(ary, l, n);
if (n % 2 == 0) // even index we are on or to the left of the oddball
l = n;
else // odd index we are to the right of the oddball
r = n-1;
}
return ary[l];
}
private static int FindBreakIndex(int[] ary, int l, int n)
{
var t = ary[n];
var r = n;
while(ary[n] != t || ary[n] == ary[n-1])
if(ary[n] == t)
{
r = n;
n = (l + r)/2;
}
else
{
l = n;
n = (l + r)/2;
}
return n;
}
Comience en el medio de la matriz y camine hacia atrás hasta que llegue a un valor que sea diferente al del centro. Verifique si el número sobre ese límite está en un índice impar o par. Si es extraño, entonces el número que aparece un número impar de veces está a la izquierda, por lo tanto, repita su búsqueda entre el principio y el límite que encontró. Si es par, entonces el número que ocurre un número impar de veces debe estar más tarde en la matriz, por lo tanto, repita la búsqueda en la mitad derecha.
Como se dijo, esto tiene un componente tanto logarítmico como lineal. Si desea mantener todo lo logarítmico, en lugar de simplemente caminar hacia atrás a través de la matriz a un valor diferente, en su lugar, desea utilizar una búsqueda binaria. A menos que espere muchas repeticiones de los mismos números, la búsqueda binaria puede no ser útil.
Esta respuesta respalda la respuesta publicada por "throwawayacct". Él merece la recompensa. Pasé un tiempo con esta pregunta y estoy totalmente convencido de que su prueba es correcta de que necesitas consultas Ω (log (n) ^ 2) para encontrar el número que ocurre un número impar de veces. Estoy convencido porque terminé recreando el mismo argumento después de solo rozar su solución.
En la solución, un adversario crea una entrada para dificultar la vida del algoritmo, pero también es simple para un analizador humano. La entrada consta de k páginas que tienen k entradas cada una. El número total de entradas es n = k ^ 2, y es importante que O (log (k)) = O (log (n)) y Ω (log (k)) = Ω (log (n)). Para hacer la entrada, el adversario hace una cadena de longitud k de la forma 00 ... 011 ... 1, con la transición en una posición arbitraria. Entonces cada símbolo en la cadena se expande en una página de longitud k de la forma aa ... abb ... b, donde en la página i, a = i y b = i + 1. La transición en cada página también está en una posición arbitraria, excepto que la paridad coincide con el símbolo desde el que se expandió la página.
Es importante comprender el "método adversario" para analizar el peor caso de un algoritmo. El adversario responde las consultas sobre la entrada del algoritmo, sin comprometerse con respuestas futuras. Las respuestas deben ser consistentes, y el juego termina cuando el adversario ha sido inmovilizado lo suficiente como para que el algoritmo llegue a una conclusión.
Con ese trasfondo, aquí hay algunas observaciones:
1) Si desea conocer la paridad de una transición en una página realizando consultas en esa página, debe conocer la posición exacta de la transición y necesita consultas Ω (log (k)). Cualquier colección de consultas restringe el punto de transición a un intervalo, y cualquier intervalo de longitud mayor que 1 tiene ambas paridades. La búsqueda más eficiente para la transición en esa página es una búsqueda binaria.
2) El punto más sutil y más importante: hay dos formas de determinar la paridad de una transición dentro de una página específica. Puede hacer suficientes consultas en esa página para encontrar la transición, o puede inferir la paridad si encuentra la misma paridad en una página anterior y una posterior. No hay escapatoria de esto o lo otro. Cualquier conjunto de consultas restringe el punto de transición en cada página a algún intervalo. La única restricción en las paridades proviene de los intervalos de longitud 1. De lo contrario, los puntos de transición son libres de moverse para tener paridades consistentes.
3) En el método adversario, no hay golpes de suerte. Por ejemplo, supongamos que su primera consulta en alguna página se dirige hacia un extremo en lugar de hacia el medio. Como el adversario no se ha comprometido a responder, él es libre de poner la transición en el lado largo.
4) El resultado final es que está obligado a sondear directamente las paridades en páginas Ω (log (k)), y el trabajo para cada uno de estos subproblemas es también Ω (log (k)).
5) Las cosas no son mucho mejores con elecciones aleatorias que con elecciones adversas. La matemática es más complicada, porque ahora puedes obtener información estadística parcial, en lugar de un estricto sí, sabes una paridad o no, no la conoces. Pero hace poca diferencia. Por ejemplo, puede asignar a cada longitud de página k ^ 2, de modo que con alta probabilidad, las primeras consultas de log (k) en cada página casi no le informan sobre la paridad en esa página. El adversario puede hacer elecciones al azar al principio y todavía funciona.
La clave es que estás buscando log (n). Eso es menos que n.
¿Caminando a través de la matriz completa, uno a la vez? Eso es n. Eso no va a funcionar.
Sabemos que los dos primeros índices en la matriz (0 y 1) deberían ser del mismo número. Lo mismo con 50 y 51, si el número impar en la matriz está detrás de ellos.
Así que encuentre el elemento medio en el conjunto, compárelo con el elemento inmediatamente después. Si el cambio en los números ocurre en el índice incorrecto, sabemos que el número impar en la matriz está delante de él; de lo contrario, es después. Con un conjunto de comparaciones, averiguamos en qué mitad de la matriz está el objetivo.
Sigue desde allí.
Mira el elemento medio de la matriz. Con un par de búsquedas binarias apropiadas, puede encontrar la primera y última aparición en la matriz. Por ejemplo, si el elemento medio es ''a'', necesitas encontrar i y j como se muestra a continuación:
[* * * * a a a a * * *]
^ ^
| |
| |
i j
¿Es j - i un número par? ¡Estás listo! De lo contrario (y esta es la clave aquí), la pregunta es ¿ es un número par o impar ? ¿Ves lo que implica este conocimiento? Entonces el resto es fácil.
No tenemos ninguna información sobre la distribución de las longitudes dentro de la matriz, y de la matriz como un todo, ¿verdad?
Entonces la longitud de la matriz podría ser 1, 11, 101, 1001 o algo así, 1 al menos sin límite superior, y debe contener al menos 1 tipo de elementos (''número'') hasta (longitud-1) / 2 + 1 elementos, para tamaños totales de 1, 11, 101: 1, 1 a 6, 1 a 51 elementos y así sucesivamente.
¿Asumiremos todos los tamaños posibles de igual probabilidad? Esto llevaría a una longitud media de subcampos de tamaño / 4, ¿no es así?
Una matriz de tamaño 5 se puede dividir en 1, 2 o 3 sublistas.
Lo que parece ser obvio no es tan obvio, si entramos en detalles.
Una matriz de tamaño 5 se puede "dividir" en una sublista de una sola manera, con el derecho discutible de llamarla "dividir". Es solo una lista de 5 elementos (aaaaa). Para evitar confusiones, supongamos que los elementos dentro de la lista son caracteres ordenados, no números (a, b, c, ...).
Divididos en dos sublistas, podrían ser (1, 4), (2, 3), (3, 2), (4, 1). (abbbb, aabbb, aaabb, aaaab).
Ahora veamos la afirmación hecha antes: ¿se supondrá que la ''división'' (5) tiene la misma probabilidad que esas 4 divisiones en 2 sublistas? ¿O debemos mezclarlos y suponer que cada partición es igualmente probable, (1/5)?
¿O podemos calcular la solución sin conocer la probabilidad de la longitud de las sublistas?
Prueba esto:
int getOddOccurrence(int ar[], int ar_size)
{
int i;
int xor = 0;
for (i=0; i < ar_size; i++)
xor = xor ^ ar[i];
return res;
}
XOR se cancelará cada vez que XOR con el mismo número, por lo que 1 ^ 1 = 0 pero 1 ^ 1 ^ 1 = 1, por lo que cada par se cancelará dejando el número impar.
Puede crear una matriz acumulativa y contar cuánto se produce cada número y luego en la matriz acumulativa encontrar el elemento que es impar. Ejemplo:
int a[]=new int[]{2,3,4,2,3,1,4,5,6,5,6,7,1};
int b[]=new int[1000];
for (int i=0;i<b.length;i++) {
b[i]=0;
}
for (Int i=0;i<a.length;i++) {
b[a[i]]++;
}
for (int i=0;i<b.length;i++) {
if ( b[i]!=0) {
if (b[i] %2==0) {
system.out.println(i); break;
}
}
Puedes usar este algoritmo:
int GetSpecialOne(int[] array, int length)
{
int specialOne = array[0];
for(int i=1; i < length; i++)
{
specialOne ^= array[i];
}
return specialOne;
}
Resuelto con la ayuda de una pregunta similar que se puede encontrar here en http://www.technicalinterviewquestions.net
Supongamos que el inicio de indexación es 0. Búsqueda binaria para el valor más pequeño incluso i tal que x [i]! = X [i + 1]; tu respuesta es x [i].
editar: debido a la demanda del público, aquí está el código
int f(int *x, int min, int max) {
int size = max;
min /= 2;
max /= 2;
while (min < max) {
int i = (min + max)/2;
if (i==0 || x[2*i-1] == x[2*i])
min = i+1;
else
max = i-1;
}
if (2*max == size || x[2*max] != x[2*max+1])
return x[2*max];
return x[2*min];
}
Tengo un algoritmo que funciona en log (N / C) * log (K), donde K es la longitud del rango máximo del mismo valor, y C es la longitud del rango que se busca.
La principal diferencia de este algoritmo respecto de la mayoría publicada anteriormente es que aprovecha el caso en el que todos los rangos del mismo valor son cortos. Encuentra los límites no mediante la búsqueda binaria en toda la matriz, sino que primero encuentra rápidamente una estimación aproximada saltando 1, 2, 4, 8, ... iteraciones (log (K) iteraciones), y luego busca binariamente rango resultante (log (K) nuevamente).
El algoritmo es el siguiente (escrito en C #):
// Finds the start of the range of equal numbers containing the index "index",
// which is assumed to be inside the array
//
// Complexity is O(log(K)) with K being the length of range
static int findRangeStart (int[] arr, int index)
{
int candidate = index;
int value = arr[index];
int step = 1;
// find the boundary for binary search:
while(candidate>=0 && arr[candidate] == value)
{
candidate -= step;
step *= 2;
}
// binary search:
int a = Math.Max(0,candidate);
int b = candidate+step/2;
while(a+1!=b)
{
int c = (a+b)/2;
if(arr[c] == value)
b = c;
else
a = c;
}
return b;
}
// Finds the index after the only "odd" range of equal numbers in the array.
// The result should be in the range (start; end]
// The "end" is considered to always be the end of some equal number range.
static int search(int[] arr, int start, int end)
{
if(arr[start] == arr[end-1])
return end;
int middle = (start+end)/2;
int rangeStart = findRangeStart(arr,middle);
if((rangeStart & 1) == 0)
return search(arr, middle, end);
return search(arr, start, rangeStart);
}
// Finds the index after the only "odd" range of equal numbers in the array
static int search(int[] arr)
{
return search(arr, 0, arr.Length);
}
Toma el elemento medio e. Use la búsqueda binaria para encontrar la primera y última ocurrencia. O (log (n)) Si es impar devuelve e. De lo contrario, recurse en el lado que tiene un número impar de elementos [....] eeee [....]
El tiempo de ejecución será log (n) + log (n / 2) + log (n / 4) .... = O (log (n) ^ 2).
Una matriz ordenada sugiere una búsqueda binaria. Tenemos que redefinir la igualdad y la comparación. Igualdad simple significa un número impar de elementos. Podemos hacer una comparación observando el índice del primer o último elemento del grupo. El primer elemento será un índice par (basado en 0) antes del grupo impar, y un índice impar después del grupo impar. Podemos encontrar el primer y el último elemento de un grupo usando la búsqueda binaria. El costo total es O ((log N) ²).
COMPROBANTE DE O ((log N) ²)
T(2) = 1 //to make the summation nice
T(N) = log(N) + T(N/2) //log(N) is finding the first/last elements
Para algunos N = 2 ^ k,
T(2^k) = (log 2^k) + T(2^(k-1))
= (log 2^k) + (log 2^(k-1)) + T(2^(k-2))
= (log 2^k) + (log 2^(k-1)) + (log 2^(k-2)) + ... + (log 2^2) + 1
= k + (k-1) + (k-2) + ... + 1
= k(k+1)/2
= (k² + k)/2
= (log(N)² + log(N))/ 2
= O(log(N)²)
Usa una tabla hash
For each element E in the input set
if E is set in the hash table
increment it''s value
else
set E in the hash table and initialize it to 0
For each key K in hash table
if K % 2 = 1
return K
Como este algoritmo es 2n, pertenece a O (n)
Teorema : todos los algoritmos deterministas para este problema sondean ubicaciones de memoria Ω (log 2 n) en el peor de los casos.
Prueba (completamente reescrito en un estilo más formal):
Deje k> 0 ser un entero impar y let n = k 2 . Describimos un adversario que fuerza (log 2 (k + 1)) 2 = Ω (log 2 n) sondas.
Llamamos subsecuencias máximas de grupos de elementos idénticos. Las posibles entradas del adversario consisten en k longitud-k segmentos x 1 x 2 ... x k . Para cada segmento xj , existe un número entero b j ∈ [0, k] tal que x j consiste en b j copias de j - 1 seguidas por k - b j copias de j. Cada grupo se superpone a lo sumo a dos segmentos, y cada segmento se superpone como máximo a dos grupos.
Group boundaries
| | | | |
0 0 1 1 1 2 2 3 3
| | | |
Segment boundaries
Dondequiera que haya un aumento de dos, asumimos un doble límite por convención.
Group boundaries
| || | |
0 0 0 2 2 2 2 3 3
Reclamo : La ubicación del límite del grupo j- ésimo (1 ≤ j ≤ k) está determinada únicamente por el segmento x j .
Prueba : es justo después de la ubicación de la memoria ((j - 1) k + b j ) th , y x j únicamente determina b j . //
Decimos que el algoritmo ha observado el j- ésimo límite de grupo en caso de que los resultados de sus sondeos de x j determinen únicamente x j . Por convención, el principio y el final de la entrada siempre se observan. Es posible que el algoritmo determine de manera única la ubicación de un límite de grupo sin observarlo.
Group boundaries
| X | | |
0 0 ? 1 2 2 3 3 3
| | | |
Segment boundaries
Dado solo 0 0?, El algoritmo no puede decir con certeza si? es un 0 o un 1. En contexto, sin embargo,? debe ser un 1, ya que de lo contrario habría tres grupos impares, y el límite del grupo en X puede inferirse. Estas inferencias pueden ser problemáticas para el adversario, pero resulta que solo pueden hacerse después de que los límites del grupo en cuestión sean "irrelevantes".
Reclamo : en cualquier punto dado durante la ejecución del algoritmo, considere el conjunto de límites de grupo que ha observado. Exactamente un par consecutivo está a una distancia impar, y el grupo impar se encuentra entre ellos.
Prueba : cada otro par consecutivo limita solo a los grupos. //
Defina la subsecuencia de longitud impar limitada por el par especial consecutivo para ser la subsecuencia relevante .
Reclamo : Ningún límite de grupo en el interior de la subsecuencia relevante está determinado de manera única. Si hay al menos uno de esos límites, entonces la identidad del grupo impar no se determina de forma exclusiva.
Prueba : sin pérdida de generalidad, suponga que cada ubicación de memoria que no se encuentra en la subsecuencia relevante ha sido explorada y que cada segmento contenido en la subsecuencia relevante tiene exactamente una ubicación que no se ha sondeado. Supongamos que el límite del grupo j th (llámelo B) se encuentra en el interior de la subsecuencia relevante. Por hipótesis, las sondas a x j determinan la ubicación de B hasta dos posibilidades consecutivas. Llamamos el uno a la distancia impar del límite observado izquierdo impar-izquierdo y el otro impar-derecho . Para ambas posibilidades, trabajamos de izquierda a derecha y arreglamos la ubicación de cada límite de grupo interior restante para que el grupo a su izquierda sea par. (Podemos hacer esto porque cada uno tiene dos posibilidades consecutivas también.) Si B está en impar-izquierda, entonces el grupo a su izquierda es el único grupo impar. Si B está en impar-derecha, entonces el último grupo en la subsecuencia relevante es el único grupo impar. Ambas son entradas válidas, por lo que el algoritmo no ha determinado de forma exclusiva ni la ubicación de B ni el grupo impar. //
Ejemplo:
Observed group boundaries; relevant subsequence marked by […]
[ ] |
0 0 Y 1 1 Z 2 3 3
| | | |
Segment boundaries
Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1
Como consecuencia de esta afirmación, el algoritmo, independientemente de cómo funcione , debe reducir la subsecuencia relevante a un grupo. Por definición, por lo tanto, debe observar algunos límites de grupo. El adversario ahora tiene la simple tarea de mantener abiertas tantas posibilidades como sea posible.
En cualquier punto dado durante la ejecución del algoritmo, el adversario está internamente comprometido con una posibilidad para cada ubicación de memoria fuera de la subsecuencia relevante. Al principio, la subsecuencia relevante es la entrada completa, por lo que no hay compromisos iniciales. Siempre que el algoritmo explore una ubicación no comprometida de x j , el adversario debe comprometerse con uno de dos valores: j - 1 o j. Si puede evitar que se observe el j- ésimo límite, elige un valor que deje al menos la mitad de las posibilidades restantes (con respecto a la observación). De lo contrario, lo elige para mantener al menos la mitad de los grupos en el intervalo relevante y los valores para los demás.
De esta forma, el adversario obliga al algoritmo a observar al menos log 2 (k + 1) límites de grupo, y al observar el j- ésimo límite de grupo, el algoritmo se ve obligado a realizar al menos log 2 (k + 1) sondas.
Extensiones:
Este resultado se extiende directamente a los algoritmos aleatorizados aleatorizando la entrada, reemplazando "en el mejor de los casos reducido a la mitad" (desde el punto de vista del algoritmo) con "al menos reducido a la mitad en expectativa", y aplicando desigualdades de concentración estándar.
También se extiende al caso donde ningún grupo puede ser más grande que s copias; en este caso, el límite inferior es Ω (log n log s) .