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.