當給出每行和每列的最大元素時，計算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

回答