当给出每行和每列的最大元素时，计算2D阵列的最大元素O（logn）

我有尺寸为n x n的二维数组。给出每行和每列的最大元素。例如，如果n = 4：当给出每行和每列的最大元素时，计算2D阵列的最大元素O（logn）

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所以我的最大值想要在O(logn)中找到整个数组的最大元素，即18。有没有这个问题的算法？

纠正我，如果我失去了一些东西，但不会从行或列最大值中找到最大只是一个'O（n）'操作？或者你在问别的东西吗？ –

给出了这些最大值。所以你不必计算它们。换句话说，你有8个元素（最大值）是上面的，你必须找到它们的最大值。 –

我尽可能地回答了下面的问题 - 如果你有任何额外的信息来给我关于最大值的列表，也许我可以改进算法。 – Assafs

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

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

如果最大列表未排序，您可以在O(n)中找到最大值，如果排序了最大列表，则可以找到最大值，如果排序，则可以找到O(1)。我无法想象在O(logn)中找不到更多数据的最大元素。

如果在时间复杂度为数组中元素的个数和单侧不是数字考虑ñ，你会得到一个近一点 - 我们可以在O溶液（开方（N）） - 但不是O（logn）。

2017-09-11 12:15:54 Assafs

我同意这一点，并假设最大值的一维数组完全没有排序，我认为我们可以做的最好的做法是将它合并成花费'O（N * lgN）'。 –

我们只需要最大行数最大值 - 所以最大行数 - 我们通过简单地进行n次交换来获得最大元素。 – Assafs

时间复杂度是基本操作和数据输入的函数。在这种情况下，我们有nxn个元素。所以如果我们为上面的数组计算（n = 4，n^n = 16），它将会是log16 = log（2^4）= 4log2 = 4的比较。我对吗？ –

给出的4 * 4示例显示行/列最大值未排序（并按照原始行/列排序）。因此，必须检查所有n行最大值（或列最大值，如果您愿意使用它们），则需要执行n个步骤。小于n，你可能会跳过真正的最大值。

所以它可以在O（n）中完成，而且毫无问题。

2017-09-11 13:00:44

回答