Tuve una pregunta de entrevista reciente en la que se me dio una matriz 2d en la que se ordena cada fila. Implemente un iterador para iterar sobre la matriz e imprimir la matriz en orden ascendente. Implemente el iterador sin usar bibliotecas. Ejemplo:

 SortedIterator sc = new SortedIterator(new int[][]{{2, 5, 8, 10, 11}, {0,1,4,6},{17, 19}});

Esto debería imprimir:

 0 1 2 4 5 6 8 10 11 17 19

MI ENFOQUE: Usé una lista dinámica para agregar cada elemento en la matriz y ordenar la lista. Use un índice cada vez que se llame a next para obtener el elemento de la lista dinámica. También tenía una llamada de función hasNext para devolver verdadero o falso si el índice es mayor o menor que la lista dinámica.

Código fuente a continuación:

 public class SortedIterator { private List<Integer> list; private index; public SortedIterator(int[][] array) { this.list = new ArrayList<>(); this.index = 0; this.setUpArrayToList(array); } private void setUpArrayToList(int[][] array) { for(int i=0;array.length;i++) { for(int j=0;j<array[i].length;j++){ list.add(array[i][j]); } } Collections.sort(list); } public int next() { int value = list.get(index); index++; return value; } public boolean hasNext() { return this.index < list.size(); } }

COMPLEJIDAD DE TIEMPO Y ESPACIO: La complejidad de tiempo será O(N*M) para insertar en la lista y nlogn para ordenar la lista. Entonces, la complejidad de tiempo general será O (NM). La Complejidad Espacial será O(N). ¿Hay un mejor enfoque?