gpt4 book ai didi

performance - 在 O(log n) 中查找排序矩阵(行 n 列)中的数字

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:13:25 24 4
gpt4 key购买 nike

<分区>

假设我有一个矩阵 (MxN),它的行和列都已排序。

  1. 每行中的所有元素均按升序排列
  2. 每列中的所有元素均按升序排列
  3. 所有元素都是整数
  4. 不能做其他假设

    示例:

    [1 5 8 20]

    [2 9 19 21]

    [12 15 25 30]

我必须找出给定数字是否存在于矩阵中(基本搜索)。我有一个运行 O(n)

的算法
int row = 0;
int col = N-1;

while (row < M && col >= 0) {
if (mat[row][col] == elem) {
return true;
} else if (mat[row][col] > elem) {
col--;
} else {
row++;
}
}

但有人问我一个O(log (MxN)) == O(Log(n)) 解决方案。有什么想法吗??

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com