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-1 每次 x 小于 currElement 递减 j 否则递增 i。