各行と列の最大要素がO（logn）で与えられたときに2次元配列の最大要素を計算します

2次元配列のサイズがn x nです。各行と列の要素の最大値が与えられます。例えば、N = 4：各行と列の最大要素がO（logn）で与えられたときに2次元配列の最大要素を計算します

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

Iはまた、10、12、18、9であり、各行の最大値と9、18、10、12だからであり、各列の最大値を有する

O(logn)に配列全体の最大要素（18）を探したいとします。この問題のアルゴリズムはありますか？

何かが見つからない場合は修正しますが、行または列の最大値から最大値を見つけるのは 'O（n）'演算ですか？あるいは何か他のことを尋ねていますか？ –

これらの最大値が与えられます。だからあなたはそれらを計算する必要はありません。言い換えれば、上記の8つの要素（最大値）があり、最大値を見つけなければなりません。 –

私は以下のように最高に答えました。もしあなたが最大値のリストを私に与えるために余分な情報があれば、おそらく私はアルゴリズムを改善することができます。 – Assafs

配列の最大要素は、デフォルトで行と列の両方の最大値です。どちらのリストにも最大の要素があるので、どちらのリストにも大きな数字が含まれないので、両方のリストで最大の要素になります。

したがって、行の最大値のリスト（または列の最大値、両方の値が必要なわけではありません）の中で最大値を見つける必要があります。

最大リストがソートされていない場合はO(n)、ソートされている場合はO(1)で最大値を見つけることができます。データがなくても最大要素がO(logn)にあるとは想像もできません。

nを、配列の要素の数であり、片側の数ではなく、時間の複雑さで考えると少し近づく - 私たちはO（sqrt（n））の解を持つことができます。 - しかし、O（logn）はありません。

2017-09-11 12:15:54 Assafs

私はこれに同意し、maximaの1D配列が完全にソートされていないと仮定して、私たちができる最良の方法は、 'O（N * lgN）'を要するmergesortです。 –

行の最大値の最大値が必要なので、すべての行の最大値にする必要があります。また、最大n個の交換を行うだけでmax要素を手に入れています。 – 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

答えて