algorithm - いいえを見つけます。O（n）のすべての異なる要素を含むnxnの配列内

Question

各行が昇順で各列が昇順になるように要素のnxn配列を指定し、O（n）アルゴリズムを考案して、配列内の特定の要素xかどうかを判断します。nxn配列のすべての要素が異なると想定できます。

誰かがこの問題の解決策を知っているかどうか教えてください。

Answer 1

最初の行の最後の列から開始します。つまり、i = 0、j = n-1

while true {
if (j< 0 || i > (n-1) )
 break; // element not found
if (array[i][j] == x)
 return i,j
else if (x < array[i][j])
 j = j -1; // and repeat
else 
 i = i+1; // and repeat
}

これはO（n）です。説明：

最初の行と最後の列から開始します。i = 0; j =n-1xがcurrElementデクリメントjよりも小さい場合は常にiをインクリメントします。