Skip to main content
se añadieron 2750 caracteres en el cuerpo
Origen Enlace
ben
  • 2.3k
  • 11
  • 19

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.

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

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.

se añadieron 83 caracteres en el cuerpo
Origen Enlace
ben
  • 2.3k
  • 11
  • 19
TreeMap<Integer, Integer>TreeSet<Integer> alreadySeenNumbers = new TreeMap<>TreeSet<>();

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

Nota: TreeSet utiliza un TreeMap a final de cuentas

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

        for (int i = 0; i < matrix.length; i++) { // O(n)
            for (int j = 0; j < matrix[0].length; j++) { // O(m)
                if (alreadySeenNumbers.containsKeycontains(matrix[i][j])) // O(log(k))
                    matrix[i][j] = -1;
                else
                    alreadySeenNumbers.putadd(matrix[i][j], 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)));
    }
}
TreeMap<Integer, Integer> alreadySeenNumbers = new TreeMap<>();

for (int i = 0; i < matrix.length; i++) { // O(n)
    for (int j = 0; j < matrix[0].length; j++) { // O(m)
        if (alreadySeenNumbers.containsKey(matrix[i][j])) // O(log(k))
            matrix[i][j] = -1;
        else
            alreadySeenNumbers.put(matrix[i][j], matrix[i][j]); // O(log(k))
    }
}
class Main {
    public static int[][] getMatrix(int[][] matrix) {
        TreeMap<Integer, Integer> alreadySeenNumbers = new TreeMap<>();

        for (int i = 0; i < matrix.length; i++) { // O(n)
            for (int j = 0; j < matrix[0].length; j++) { // O(m)
                if (alreadySeenNumbers.containsKey(matrix[i][j])) // O(log(k))
                    matrix[i][j] = -1;
                else
                    alreadySeenNumbers.put(matrix[i][j], 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)));
    }
}
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

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)));
    }
}
Origen Enlace
ben
  • 2.3k
  • 11
  • 19

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.

TreeMap<Integer, Integer> alreadySeenNumbers = new TreeMap<>();

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

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) {
        TreeMap<Integer, Integer> alreadySeenNumbers = new TreeMap<>();

        for (int i = 0; i < matrix.length; i++) { // O(n)
            for (int j = 0; j < matrix[0].length; j++) { // O(m)
                if (alreadySeenNumbers.containsKey(matrix[i][j])) // O(log(k))
                    matrix[i][j] = -1;
                else
                    alreadySeenNumbers.put(matrix[i][j], 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