在 C++ 中按行和列排序的矩阵中查找

问题指定我们给定一个整数 X 和一个行向和列向排序矩阵。我们必须确定提供的数字 "X" 是否已在此矩阵中找到；如果找到，显示 X 的确切位置；如果未找到，则将其打印为 "未找到"。

示例

输入

{ {12, 2, 13, 9},

{58 6, 7, 8},

{9, 11, 61, 62},

{19, 43, 15, 45} }

要查找的元素是 X = 8。

您可以遍历整个矩阵，从左上角 (第 1 行，第 1 列) 开始，并将每个成员与所需值（在本例中为 8）进行比较。

第一行中的比较

索引 1,1 处的元素：1（不等于 8）

索引 1,2 处的元素：2（不等于 8）

索引 1,3 处的元素：3（不等于 8）

索引 1,4 处的元素：4（不等于 8）

在第二行中，有一个比较

位置 2: 1 元素：5（不等于 8）

索引 2,2 处的元素：6（不等于 8）

索引 2,3 处的元素：7（不等于 8）

索引 2,4 处的元素：8（等于 8）

输出

因此，元素 8 出现在第二行、第四列，位置 2,4。

朴素方法

在朴素技术中，我们可以扫描整个行向和列向排序矩阵并搜索提供的元素。如果找到，打印其位置。

算法步骤 L=

• 运行嵌套 for 循环，外部 for 循环用于行，内部 for 循环用于列。
• 如果每个元素和 X 都相等，则显示 "在以下位置找到：" 行号和列号。
• 如果矩阵中缺少某个元素，则打印 "未找到"。

文件名：Row_col_index.cpp

输出

The element found At 2,4

复杂性分析

时间复杂度： O(R*C)

解释：R 是此行向和列向排序矩阵中的行数，C 是此行向和列向排序矩阵中的列数。由于我们访问了整个数组，因此此程序的时间复杂度变为 O(R*C)。

空间复杂度：O(1)

解释： 不需要额外空间。

贪婪方法（优化）

目标是在每次比较中删除行或列，直到我们达到所需的数字或超出范围。我们将从矩阵的右上角开始。这种方法有三种可能的方式。

• 假设元素 X 超出当前数字。在这种情况下，它表示当前行中的所有组件都小于X（因为行已排序，并且我们处于正确的位置）；我们可以跳过当前行并继续到下一行以获取数字 X。如果元素 X 小于当前值。在这种情况下，它表示当前列中的所有组件（列已排序，并且我们位于底部）都大于 X。因此，我们可以跳过当前列并转到上一列以查找该数字。
• 如果元素 X 等于当前数字，则打印"元素在以下位置找到"行号和列号，然后我们的搜索结束。
• 通过这种方式，我们可以搜索行向和列向排序矩阵。

算法步骤

1. 令 X 为要查找的元素。
2. 创建两个变量，i = 0 和 j = c-1，分别表示第 0 行和最后一列。
3. 重复直到 i!= r，其中 r 是总行数或 j0。
4. 如果当前数字大于 X，则减小 j；否则，如果当前数字小于 X，则增加 i。
5. 如果找到元素，则打印 i 和 j。
6. 否则打印 "未找到"。

文件名：Row_col_index2.cpp

输出

The element has been found At 2,4

复杂性分析

时间复杂度：O(N+M)

解释：R 是此行向和列向排序矩阵中的总行数，C 是此行向和列向排序矩阵中的总列数。最坏情况时间复杂度是 O(N+M)，因为我们只读取一行和一列。

空间复杂度：O(1)

解释： 不需要额外空间。