arrays - programacion - Encuentre la fila que representa el entero más pequeño en una matriz ordenada por filas
matriz c++ ejemplos (14)
¿Qué hay de bucle de cada línea en orden inverso y verificar dónde terminan los 1 y los ceros comienzan?
De hecho, está garantizado que en NxN , el peor caso es que 0 no estará allí. Entonces puede verificar las últimas 2 entradas de cada fila. Lo que lo hace lineal.
Como mi explicación no fue entendida, aquí está en un pseudo código:
int lowestRow = -1;
for (k = 0; k < array.length; k ++) {
byte[] row = array[k];
if (row[row.length - 1] == 0) {
lowestRow = k;
break;
}
if (row[row.length - 2] == 0) {
lowestRow = k;
//possibly look for all-zeroes, so not breaking
}
}
Me hicieron esta pregunta en una reciente entrevista telefónica de Java:
Te dan una matriz NxN binaria (0-1) con las siguientes propiedades:
- Cada fila está ordenada (secuencia de 0 seguida por secuencia de 1)
- Cada fila representa un entero sin signo (leyendo los bits)
- Cada fila es única
Ejemplo:
0 1 1
1 1 1
0 0 1
Los valores de bit en cada fila se ordenan y las filas representan los enteros 3, 7 y 1.
Encuentra la fila que representa el entero más pequeño. En el ejemplo anterior, la respuesta es la fila 3, que representa el número entero 1.
Empecé con la fuerza bruta de complejidad cuadrática. El entrevistador respondió diciendo que no estaba explotando la propiedad clasificada.
Después de pensar mucho, utilicé la búsqueda binaria en cada fila y llegó a O (nlogn). Me preguntó si podía mejorar más. Pensé mucho pero no pude mejorar.
Apreciaría si alguien puede dar algún consejo para impublicarlo.
Otro ejemplo:
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
La respuesta será la fila 3, que representa el número entero 0.
Agregaría esto como un comentario a la respuesta de Jeremy si pudiera, porque su solución es en su mayoría correcta. Además, me gusta el enfoque. En muchos casos, será MUCHO más rápido que otras respuestas. Hay un posible problema. Si "Cada fila está ordenada" no significa que todos se desplazan hacia la derecha, pero tiene alguna otra implicación (puedo pensar en un par de implicaciones. Necesitaría más de la persona que hace la pregunta). Un problema ... ¿qué hay acerca de 0011 y 0010? Las filas están ordenadas podrían significar que el algoritmo que está implementando ya está siendo utilizado. El algoritmo especificado en su respuesta no puede distinguir entre los dos. Guardaría el índice de ambas respuestas en una matriz. Si la longitud de la matriz es 1, entonces tienes una solución; de lo contrario, necesitarás recurrir más ... solo un pensamiento. Si alguien lee esto y puede publicar comentarios en otras publicaciones, por favor haz referencia a esto en un comentario a su publicación. Es un problema serio, y sería molesto tener una respuesta técnicamente incorrecta para obtener el cheque. Si mi comentario es agregado, borraré mi respuesta por completo.
Comience con la fila 1. Vaya a la derecha hasta que llegue a la primera 1 . Luego baje a la fila 2, pero permanezca en la misma columna y repita el proceso de ir hacia la derecha hasta que llegue a 1 . Haz esto repetidamente. La fila en la que duró el último paso es su respuesta.
Esta es una solución O (N + M) (para una matriz NxM, u O (N) para una matriz NxN cuadrada como se da en la pregunta).
Usando su ejemplo de:
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
El . está aquí representa el camino recorrido:
. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .
Esta solución funciona en matrices no cuadradas, conservando la peor eficiencia de O (N + M) para una matriz NxM.
¿Por qué funciona esto? La garantía de que los números serán ordenados significa que cada fila será una serie de 0 seguida de una serie de 1. Entonces, la magnitud de una fila es equivalente a qué tan lejos puede llegar antes de llegar a 1. Entonces, si una fila puede llevarlo más allá simplemente siguiendo los 0, entonces debe ser más largo que todo lo que hemos procesado anteriormente.
Código de Python:
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
ans, j = 0, 0
for i, row in enumerate(li):
while j < len(row) and row[j] == 0:
j += 1
ans = i
print "Row", ans+1, "".join(map(str, li[ans]))
También hay una solución más simple, debido a las limitaciones de tener siempre una matriz NxN cuadrada y filas distintas juntas. Juntos significan que la fila con el valor más bajo será 0 0 ... 0 1 o 0 0 ... 0 0 . Esto es porque hay N de N + 1 números posibles representados en la matriz, por lo que el número "faltante" es 0 (en cuyo caso el valor más pequeño representado es 1) o es otra cosa (el valor más pequeño es 0).
Con este conocimiento, verificamos la columna en segundo lugar desde la derecha para un 0. Cuando encontramos uno, miramos hacia la derecha y si contiene otro 0 tenemos nuestra respuesta (solo puede haber una fila que termina en un 0 ). De lo contrario, continuamos buscando en la columna por otro 0. Si no encontramos otro 0, el primero que encontramos fue la fila que estamos buscando (solo puede haber una fila que termina en 01 y dado que no hubo ninguna que termine) en 00 , este es el más pequeño).
Código de Python:
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
for i, row in enumerate(li):
if row[-2] == 0:
ans = i
if row[-1] == 0:
break
print "Row", ans+1, "".join(map(str, li[ans]))
Esa solución responde a la pregunta con la menor dificultad en O (N), pero generalizarla para manejar matrices NxM no cuadradas o números no distintos hará que su peor rendimiento sea O (N ^ 2). Personalmente prefiero la primera solución.
Como los bits de cada fila están ordenados, una vez que haya encontrado un bit de 1, todos los bits de la derecha también deben ser 1. En otras palabras, la matriz solo almacena valores de la forma 2 ^ n-1.
Entonces, la respuesta es que la fila con la mayor cantidad de entradas cero es la más pequeña.
Sin embargo, dado que solo pueden estar presentes 2 ** m-1 entradas, y hay n de ellas, y no hay dos iguales, podemos deducir más: para cualquier N, hay N + 1 de tales valores. Entonces 0 o 1 deben estar presentes ya que sabemos que no hay duplicados.
Así que busque una fila vacía (que es la única con la columna a la derecha cero). Si no lo encuentras, la respuesta es 1, de lo contrario es 0.
EN)
Como los números son únicos y como los dígitos están ordenados, es bastante claro que para cualquier valor de N, el número más pequeño puede ser cualquiera de la forma [0 (N-1 veces) seguido de 1] o 0 (N veces) .
Por ejemplo, para N = 4, el número más pequeño puede ser 0001 o 0000.
En otras palabras, el segundo último dígito del número que queremos encontrar TIENE que ser 0. Y el último dígito puede ser 0 o 1
Este problema se reduce a encontrar estos patrones en la matriz, lo que se puede hacer utilizando un simple bucle for
int rowNum = -1;
for(int i=0;i<N;i++)
{
if(arr[i][N-2]==0) //Second last digit is 0. Hence the number could be min.
{
rowNum = i;
if(arr[i][N-1]==1) // If number of the form 0001 was found, keep looking for 0000
{
continue;
}
else
//If number of the form 0000 was found, exit.
//No other number can be lesser than 0000
{
break;
}
}
}
return rowNum;
Este algoritmo tendría complejidad O (n)
Desea encontrar una fila con un número máximo de ceros.
- Comience en
arr[0][0] - Si es
0, verifique el elemento hacia la derecha,arr[0][1]. - Si no es
0, omita esa fila y comience a verificar el elemento en la siguiente fila debajo del elemento actual.
Sigue haciendo hasta que pases la última fila / última columna o encuentres una fila con todos los ceros.
Algoritmo:
i = 0
j = 0
answer = 0
# continue till i is a valid index.
while(i<N)
# continue till j is valid index and ele is 0.
while(j < N AND arr[i][j] == 0)
# move towards right.
j++
#update answer.
answer = i
# found a row with all zeros.
if(j == N)
break all loops.
end-if
end-while
# skip current row..continue on next row.
i++
end-while
print answer
La complejidad de esto es O(N+N) que es O(N) , que es lineal.
Pregunta relacionada que hace uso de exactamente el mismo truco
El número más pequeño puede ser 0, que se parece a (0000 ... 0000) o 1, que se parece a (0000 ... 0001).
Cada número mayor parece (xxxx ... xx11). Por lo tanto, debe verificar el penúltimo dígito en cada fila. Si es 0, compruebe si el último dígito es 0. Si lo es, es el número más pequeño. De lo contrario, recuerde el número de fila y continúe buscando fila con 0 en el penúltimo dígito. Si lo encuentras, este será el número más pequeño. Si no, el primer número encontrado es el más pequeño.
Esta es la solución con N + 1 pasos (peor escenario) que es O (N) complejidad.
Encuentra qué fila tiene el primer valor distinto de cero en la columna más lejana. Si es binario, con el MSB a la izquierda y el LSB a la derecha, la respuesta es la fila que comienza con la mayor cantidad de ceros.
He escrito un algoritmo O (n), similar a lo que se ha indicado anteriormente, comenzamos desde la esquina superior izquierda y trabajamos hacia abajo:
a = [
[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]
]
a2 = [
[0, 0, 0, 0],
[0, 1, 1, 1],
[0, 0, 0, 1],
[1, 1, 1, 1]
]
def search(a):
n = len(a)
c = 0
r = 0
best_row = 0
while c<n and r<n:
if a[r][c] == 0:
c += 1
else:
best_row = r
r += 1
if c==n : best_row = r
print( " best row: %d" % best_row )
search( a )
search( a2 )
No sé si es admitido, pero si está ordenado, no necesita simplemente convertir cada fila en un número decimal y elegir la fila con la inferior. ejemplo:
[0111] -> 7
[0011] -> 3
[0000] -> 0
[0001] -> 1
La solución es la fila con valor 0. ¿O?
Tienes que comenzar con la última columna, y verificar si la suma del elemento es N-1, una vez que has encontrado la columna con la suma = N-1, busca la columna que contiene un 0 y esta es la que estás buscando. ...
Una versión optimizada de @codaddict
int best = N;
int answer = -1;
for(int i=0;i<N;i++)
for(int j=0;j<best;j++)
if (arr[i][j] != 0) {
best = j;
answer = i;
}
Los bucles internos se detienen tan pronto como determina que esta fila no será mejor que la respuesta actual. Esto podría cortar una gran cantidad de búsquedas en las filas que son más largas que la mejor respuesta hasta el momento.
el número más bajo debe ser 0 o 1. (porque no hay duplicaciones y las filas están ordenadas). todo lo que tienes que hacer es ir a la última columna, si ti contiene 0 el número más bajo es 0, de lo contrario, el número más bajo es 1.
EDITAR - explicación
En N filas con la restricción que sació, puede haber un máximo de N+1 valores únicos.
así que seguro que al menos 0 o 1 deben estar en la matriz ...
Editar 2 - algoritmo
//assuming the matrix is 0 indexed base
for i = 0...N-1
if M[i][N-1] == 0
return "Value is 0 in row i";
for i = 0...N-1
if M[i][N-2] == 0
return "Value is 1 in row i";
//because of the explanation above the flow will never reach here.
Start at the top-left.
The first row is the best row so far.
Repeat until you reach the bottom:
If you''re not already over a 1:
Go right until you find a 1.
This row is the best row so far.
Go down one row.
Report the best row that was found.
Nunca subes o bajas, solo bajas (n-1) veces y no haces más de (n-1) veces, haciendo esto O (n). Esto explota la clasificación al darse cuenta de que nunca tienes que ir a la izquierda para buscar un 1 - si hay un 1 en algún lugar a la izquierda, entonces también hay un 1 en el lugar actual (y por lo tanto, el número en esta fila es al menos tan grande como el de la fila anterior).