1

Tengo este ejercicio en el cual debo cambiar todo número repetido por -1 excepto el primero que salga por ejemplo si en el primer índice hay un 2 y en el segundo también solo se debe cambiar el segundo, el primero debe permanecer como 2, ahora tengo este ejercicio que me hace eso, pero en la primer fila no. adjunto mi código.

   public int[][] getMatrix(int matrix[][]) {
        int count = 0;
        for (int x = 0; x < matrix.length; x++) {
            for (int k = 0; k < matrix[0].length; k++) {
                for (int i = 0; i < matrix.length; i++) {
                    for (int j = 0; j < matrix[0].length; j++) {
                       if(i != count){ // En esta línea incluso intenté algo como if(i != x && j != k); pero fue el resultado equivocado también.
                        if (matrix[i][j] == matrix[x][k] && matrix[i][j] != -1) {
                            matrix[i][j] = -1;
                        } // If
                       } // If externo
                    } // For j
                } // For i
            } // For k
            count++;
        } // For x
        return matrix;
    } // Fin de método

La matriz que usé fue esta:

int matriz[][] = {{2, 5, 2, 6, 7},
                  {5, 2, 6, 9, 7},
                  {2, 3, 7, 2, 7}};

y el resultado de salida fue este.

[[2, 5, 2, 6, 7], [-1, -1, -1, 9, -1], [-1, 3, -1, -1, -1]]

2 respuestas 2

2

Una manera (a mi parecer mas sencilla para tu caso) es utilizar un ArrayList para almacenar tu matriz y comprobar si existen números repetidos para cambiarlos por -1

Creamos el ArrayList

ArrayList<Integer> list = new ArrayList<Integer>();

Recorremos la matriz y realizamos la comprobación de si existen o no los numero para guárdalos en la lista o cambiarlos por -1

for (int i = 0; i < matriz.length; i++) {
    for (int j = 0; j < matriz[0].length; j++) {
        
        if (list.contains(matriz[i][j])) {
            matriz[i][j] = -1;
                    
        } else {
            list.add(matriz[i][j]);
        }           
    }
}

Tan solo nos queda ver el resultado, para ello nos creamos un método para visualizar la matriz:

public static void showMatriz(int[][] arr) {

    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[0].length; j++) {
            System.out.print(" " + arr[i][j]);
        }
    }
    System.out.println();
}

Ejemplo completo:

import java.util.ArrayList;

public class test {

    public static void main(String[] args) {

        int matriz[][] = { { 2, 5, 2, 6, 7 }, { 5, 2, 6, 9, 7 }, { 2, 3, 7, 2, 7 } };
        showMatriz(matriz);
        

        ArrayList<Integer> list = new ArrayList<Integer>();

        for (int i = 0; i < matriz.length; i++) {
            for (int j = 0; j < matriz[0].length; j++) {
                if (list.contains(matriz[i][j])) {
                    matriz[i][j] = -1;
                    
                } else {
                    list.add(matriz[i][j]);
                }           
            }
        }
        showMatriz(matriz);
    }

    public static void showMatriz(int[][] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(" " + arr[i][j]);
            }
        }

        System.out.println();
    }
}

Output:

[[2, 5, -1, 6, 7], [-1, -1, -1, 9, -1], [-1, 3, -1, -1, -1]]
2

Complejidad O(n^2m^2) no es muy buena, es mejor hacer la búsqueda utilizando un árbol. Java por defecto creo que no tiene una clase con la implementación de un BST numérico, pero por fortuna tiene la clase TreeMap que implementa un RedBlack tree. Aunque obviamente lo mejor quizá sería hacer una implementación propia de un árbol más sencillo que almacene simplemente valores numéricos pues TreeMap es demasiado para este simple ejercicio.

Como sea, el algoritmo es muy sencillo, simplemente hay que recorrer toda la matriz y agregar al árbol el valor SI es que no está ya previamente en el árbol, en caso de que el valor se encuentre ya en el árbol, simplemente hay que sustituirlo por -1 , eso lo hace el siguiente código.

TreeSet<Integer> alreadySeenNumbers = new TreeSet<>();

for (int i = 0; i < matrix.length; i++) { // O(n)
    for (int j = 0; j < matrix[0].length; j++) { // O(m)
        if (alreadySeenNumbers.contains(matrix[i][j])) // O(log(k))
            matrix[i][j] = -1;
        else
            alreadySeenNumbers.add(matrix[i][j]); // O(log(k))
    }
}

Nota: TreeSet utiliza un TreeMap a final de cuentas

Como ves no solo es más sencillo, sino su comportamiendo asintótico es mucho mejor O(n m log(k)), k siendo el número de elementos en el árbol k < nm.

El código completo es el siguiente.

class Main {
    public static int[][] getMatrix(int[][] matrix) {
        TreeSet<Integer> alreadySeenNumbers = new TreeSet<>();

        for (int i = 0; i < matrix.length; i++) { // O(n)
            for (int j = 0; j < matrix[0].length; j++) { // O(m)
                if (alreadySeenNumbers.contains(matrix[i][j])) // O(log(k))
                    matrix[i][j] = -1;
                else
                    alreadySeenNumbers.add(matrix[i][j]); // O(log(k))
            }
        }

        return matrix;
    }

    public static void main(String... args){
        int matrix[][] = {
            {2, 5, 2, 6, 7},
            {5, 2, 6, 9, 7},
            {2, 3, 7, 2, 7}
        };

        System.out.println(Arrays.deepToString(getMatrix(matrix)));
    }
}

Por último getMatrix no necesita retornar la matriz, porque recibe una copia de la referencia de la matriz como argumento y modifica su valor, esto a no ser que se requiera guardar el estado previo de la matriz, en cuyo caso habría que pasarle una copia de la matriz original.

Edit: Implementando un BST

Si no se desea utilizar un TreeMap o un TreeSet, se puede implementar un árbol desde 0.

Esta es una implementación realmente muy muy muy sencilla de un BST, evidentemente le hacen falta operaciones y lo más importante, que sea autobalanceable para garantizar los tiempos O(log(k)), pero creo que servirá para darte una idea de cómo continuar.

class Main {
    public static int[][] getMatrix(int[][] matrix) {
        BST alreadySeenNumbers = new BST();

        for (int i = 0; i < matrix.length; i++) { // O(n)
            for (int j = 0; j < matrix[0].length; j++) { // O(m)
                if (alreadySeenNumbers.contains(matrix[i][j])) // O(log(k))
                    matrix[i][j] = -1;
                else
                    alreadySeenNumbers.add(matrix[i][j]); // O(log(k))
            }
        }

        return matrix;
    }

    public static void main(String... args){
        int matrix[][] = {
            {2, 5, 2, 6, 7},
            {5, 2, 6, 9, 7},
            {2, 3, 7, 2, 7}
        };

        System.out.println(Arrays.deepToString(getMatrix(matrix)));
    }

    private static class BSTNode {
        private BSTNode leftNode;
        private BSTNode rightNode;
        private final int value;

        public BSTNode(int value) {
            this.value = value;
        }

        public void setLeftNode(BSTNode leftNode) {
            this.leftNode = leftNode;
        }

        public void setRightNode(BSTNode rightNode) {
            this.rightNode = rightNode;
        }

        public BSTNode getLeftNode() {
            return leftNode;
        }

        public BSTNode getRightNode() {
            return rightNode;
        }

        public int getValue() {
            return value;
        }
    }

    private static class BST {
        private BSTNode root;

        public void add(int value) {
            if (root == null) {
                root = new BSTNode(value);
                return;
            }

            BSTNode tmpRoot = root;
            boolean added = false;

            while (true) {
                if (value > tmpRoot.getValue()) {// look to the right
                    if (tmpRoot.getRightNode() == null) {
                        tmpRoot.setRightNode(new BSTNode(value));
                        break;
                    }
                    tmpRoot = tmpRoot.getRightNode();
                } else { // look to the left
                    if (tmpRoot.getLeftNode() == null) {
                        tmpRoot.setLeftNode(new BSTNode(value));
                        break;
                    }
                    tmpRoot = tmpRoot.getLeftNode();
                }
            }
        }

        public boolean contains(int value) {
            BSTNode tmpRoot = root;

            while (tmpRoot != null) {
                if (value == tmpRoot.getValue())
                    return true;

                if (value > tmpRoot.getValue()) // look to the right
                    tmpRoot = tmpRoot.getRightNode();
                else // look to the left
                    tmpRoot = tmpRoot.getLeftNode();
            }

            return false;
        }
    }
}

El output para ambos programas es el mismo [[2, 5, -1, 6, 7], [-1, -1, -1, 9, -1], [-1, 3, -1, -1, -1]], sin embargo, no estaría de más realizar tests de stress.

7
  • Pues me gusta la información que me brindaste, es algo que me va a servir mucho para avanzar y tener en cuenta para más adelante, pero en este momento quería hacerlo de alguna de esta forma, sin usar librerías o algo por el estilo, pero nuevamente te agradezco por la información. Commented el 27 ene. 2021 a las 21:11
  • @carloszamora TreeMap está incluido en la API de java, no se utiliza ninguna librería externa. ¿Te refieres a hacer "a mano" la implementación?
    – ben
    Commented el 27 ene. 2021 a las 21:14
  • si, disculpame por el comentario ignorante xd, a eso me refiero Commented el 27 ene. 2021 a las 21:15
  • @carloszamora edité mi respuesta con la implementación hecha "a mano", sin utilizar TreeMap
    – ben
    Commented el 27 ene. 2021 a las 21:38
  • Si es un ejercicio de clase y están aprendiendo a recorrer Arrays, lo mismo empezar a hablarle de complejidad y del uso de árboles está un poco de más... Si quieres hacer una casa, no empiezas comprando los muebles de las habitaciones, empiezas por los cimientos y manchando todo, ya se irá limpiando luego :P
    – Benito-B
    Commented el 27 ene. 2021 a las 21:57

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.