java - 当给定每行和每列的最大元素时，计算二维数组的最大元素，时间复杂度为 O(logn)

Question

我有大小为 n x n 的二维数组。给出了每行和每列的最大值元素。例如，如果 n = 4:

int[][] arr = {{2, 3, 10, 1} 
               {9, 2, 8, 12},
               {5, 18, 2, 10},
               {7, 9, 3, 5}}

我还有每行的最大值 10、12、18、9 和每列的最大值 9、18、10、12。所以我想找到整个数组的最大元素，即18，在 O(logn) 中。这个问题有算法吗？

Answer 1

默认情况下，数组中的最大元素是其行和列的最大值。我们知道这两个列表都不会包含更大的数字，因为它是最大元素 - 因此它将是两个列表中最大的。

因此，我们只需要找到行最大值列表中的最大值(或列最大值，您不需要两者)。

如果最大列表未排序，则可以在 O(n) 中找到最大值，如果已排序，则可以在 O(1) 中找到最大值。我无法想象在没有更多数据的情况下如何在 O(logn) 中找到最大元素。

如果您将时间复杂度中的 n 视为数组中元素的数量而不是单边的数量，您会更接近一点 - 我们可以在 O(sqrt (n)) - 但不是 O(logn)。