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.