java - 将每行排序的二维数组转换为一维数组，并使用迭代器打印出值

Question

我最近有一个面试问题，其中给出了一个二维数组，其中每行都已排序。实现一个迭代器来迭代数组并按升序打印数组。不使用库实现迭代器。示例:

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

这应该打印出来:

0
1
2
4
5
6
8
10
11
17
19

我的方法:我使用动态列表来添加数组中的每个元素并对列表进行排序。每次调用 next 时都使用索引从动态列表中获取元素。如果索引大于或小于动态列表，还有一个函数调用 hasNext 返回 true 或 false。

源代码如下:

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();
   }
 }

时间和空间复杂度:插入列表的时间复杂度为 O(N*M)，对列表排序的时间复杂度为 nlogn。所以总体时间复杂度为O(NM)。空间复杂度将为 O(N)。有更好的方法吗？

Answer 1

这似乎是很好的方法，因为在其他情况下，您的操作会变得更加复杂，O(N*2) 或更高