una - suma de matrices en java con metodos

Eliminación de números negativos de una matriz en Java

Question

Mi objetivo es eliminar todos los números negativos de una matriz en Java.

He escrito el siguiente código. ¿Cómo puedo mejorar la complejidad del código o hay un buen algoritmo?

public static void main(String[] args) {
int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 };
System.out.println(Arrays.toString(removeNegativeNumbers(array)));
}
public static int[] removeNegativeNumbers(int[] num) {
List<Integer> list = new ArrayList<>();
for (int n : num) {
if (n >= 0) {
list.add(n);
}
}
int[] result = new int[list.size()];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(i).intValue();
}
return result;
}

Answer 1

¿Cómo puedo mejorar la complejidad del código o hay un buen algoritmo?

Aquí hay un algoritmo O(n) lineal con espacio constante (descuidando el espacio que necesitamos para la matriz de salida). Cuando un elemento no es negativo, copie el elemento y avance tanto la matriz de salida como el buscador de matriz de entrada. Y cuando el elemento es negativo, avance solo el buscador de matriz de entrada (indx) y evite copiar en la matriz de salida.

public static int[] removeNegativeNumbers(int[] num) {
int[] output = new int[num.length];
int k = 0;
for(int i = 0; i < num.length; i++) {
if(num[i] >= 0) {
output[k++] = num[i];
}
}
return Arrays.copyOfRange(output, 0, k);
}

Solución de espacio eficiente

Puede hacer el algoritmo en el lugar transformando la matriz de entrada para mantener la salida de manera similar a la inserción para evitar la sobrecarga de espacio de la matriz de salida.

public static int removeNegativeNumbers(int[] num) {
int k = 0;
for(int i = 0; i < num.length; i++) {
if(num[i] >= 0) {
num[k++] = num[i];
}
}
// Now input array is holding the output data
// Return the length of output array
return k;
}
// Usage: int newLen = removeNegativeNumbers(array);

Esto se denomina técnica de dos punteros , muy simple pero útil para resolver muchos rompecabezas clásicos como la eliminación de duplicaciones de matrices, fusionando dos matrices ordenadas, intersección de dos matrices ordenadas, etc.

Answer 2

¿Qué pasa con las secuencias de Java 8?

Arrays.stream(num).filter(s -> s >= 0).toArray();

Answer 3

Dado que necesariamente deberá mirar cada elemento individual para determinar si es menor que 0, el tiempo de ejecución debe ser al menos O (n). Dado que el espacio necesario para almacenar la entrada es O (n), el espacio es al menos O (n). Su solución se ejecuta en tiempo O (n) con complejidad O (n), por lo tanto, ninguna solución puede tener mejor complejidad de espacio o tiempo de ejecución que su solución

Sin embargo, podemos obtener mejores resultados si asumimos que la matriz está ordenada. Luego, hacemos una búsqueda binaria de 0. Si tenemos una manera de devolver la sub-matriz con tiempo constante (p. Ej., La magia del puntero en C, o simplemente devolviendo el índice de inicio para ser leído), entonces el algoritmo tendría una O ( registro n) tiempo.

Answer 4

Esto lo hará en el lugar con una sola iteración:

Mantenga 2 índices: src y dst en la matriz original. ambos se inicializan a 0.

cuando un número es positivo, cópielo de num[src] a num[dst] y avance ambos índices

cuando un número es negativo, simplemente avanza src .

devuelve la matriz original con dst como su nuevo tamaño.

public static int removeNegativeNumbers(int[] num) {
int dst=0;
for (int src=0 ; src<num.length ; ++src)
if (num[src]>=0)
num[dst++] = num[src];
return dst;
}

Answer 5

No creo que podamos mejorar en términos de eficiencia que @ kaidul-islam respuesta (y @ user6904265 en términos de concisión).

Solo estoy agregando una solución que debería tener algún valor en un escenario muy específico, donde los negativos rara vez aparecen y la matriz es muy grande.

La idea básica es diferir la copia real hasta que se encuentre un valor negativo y luego copiar con System.arraycopy. En caso de que no se encuentre ningún negativo, se devolverá la matriz de origen.

import java.util.*;
public class NotNegativeTest {
public static void main(String[] args) {
int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 };
System.out.println(Arrays.toString(removeNegativeNumbers(array)));
}
public static int[] removeNegativeNumbers(int[] num) {
int[] output = new int[num.length];
int k = 0;
int i = 0;
int last=-1;
int howmany=0;
while(i < num.length) {
if(num[i] < 0) {
howmany=i-last-1;
switch(howmany) {
case 0: break;
case 1:
output[k]=num[last+1];
k++;
break;
default:
System.arraycopy(num, last+1, output, k, howmany);
k+=howmany;
}
last=i;
}
i++;
}
if (last>=0) {
if(last!=i-1) {
howmany=i-last-1;
System.arraycopy(num, last+1, output, k, howmany);
k+=howmany;
}
} else {
return num;
}
return Arrays.copyOfRange(output, 0, k);
}
}

He encontrado el tiempo para escribir una marca de microbios JMH.

He usado estas configuraciones usadas:

Options opts = new OptionsBuilder()
.include(MyBenchmark.class.getSimpleName())
.mode(Mode.AverageTime)
.warmupIterations(1)
.warmupTime(TimeValue.seconds(5))
.measurementIterations(10)
.measurementTime(TimeValue.seconds(5))
.jvmArgs("-server")
.forks(1)
.build();
new Runner(opts).run();

(descargo de responsabilidad: mi primera prueba JMH, así que si alguien tiene algunas sugerencias, estaré encantado de cambiarlo y actualizar los resultados)

Y aquí están los resultados:

# Run complete. Total time: 00:02:54
Benchmark Mode Cnt Score Error Units
MyBenchmark.testMethodUser6904265 avgt 10 0,201 ± 0,040 s/op
MyBenchmark.testMethodInsac avgt 10 0,093 ± 0,022 s/op
MyBenchmark.testMethodKaidul avgt 10 0,124 ± 0,029 s/op

Ahora, antes de animarme, eche un vistazo a qué tan sesgada fue la prueba:

 int[] array = new int[10000000];
array[0]=-5;
array[10000]=-3;
array[40000]=-3;
array[8000000]=-3;
int[] answer=NotNegativeTest.removeNegativeNumbers(array);

Entonces, lo que hay que notar es que no gané mi método (la prueba fue escrita para mi método para ganar :-) sino cuán cerca fue el método genérico del kaidul-islam para minar incluso en este escenario extremo.

ACTUALIZADO: aquí está el enlace al jmh benchmark que escribí para que pueda verificar un escenario más realista (si alguien encuentra problemas con la configuración de la prueba, hágamelo saber). Hay una dependencia en Trove para una prueba que hice en otra respuesta.

Answer 6

Siga el código de abajo (Java 8)

int test[] = new int[] { 15, -40, -35, 45, -15 };
// here we can take the test array in to stream and filter with condition (>=0).
int[] positives = Arrays.stream(test).filter(x -> x >= 0).toArray();
System.out.println("Here is the positive array elements");
for (int i : positives) {
System.out.print(i + "/t");
}

Answer 7

public static int[] removeNegativeNumbers(int[] num) {
List<Integer> list = new ArrayList<>();
for (int n : num) {
if (n >= 0) {
list.add(n);
}
}
return list.toArray(new int[list.size()]);
}