数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何使用 C# 在按行按列递增的矩阵里搜索？
解决此问题的基本方法是扫描存储在输入矩阵中的所有元素以搜索给定的键。如果矩阵的大小为 MxN，则此线性搜索方法的代价为 O(MN) 时间。
矩阵可以视为已排序的一维数组。如果输入矩阵中的所有行按从上到下的顺序连在一起，它将形成已排序的一维数组。在这种情况下，二分搜索算法适用于此 2D 数组。下面这段代码开发了一个函数 SearchRowwiseColumnWiseMatrix，它接受一个二维数组和搜索键作为输入，并根据搜索键的查找成功或失败返回 true 或 false。
示例
public class Matrix{
public bool SearchRowwiseColumnWiseMatrix(int[,] mat, int searchElement){
int col = getMatrixColSize(mat);
int start = 0;
int last = mat.Length - 1;
while (start <= last){
int mid = start + (last - start) / 2;
int mid_element = mat[mid / col, mid % col];
if (searchElement == mid_element){
return true;
}
else if (searchElement < mid_element){
last = mid - 1;
}
else{
start = mid + 1;
}
}
return false;
}
private int getMatrixRowSize(int[,] mat){
return mat.GetLength(0);
}
private int getMatrixColSize(int[,] mat){
return mat.GetLength(1);
}
}
static void Main(string[] args){
Matrix m = new Matrix();
int[,] mat = new int[3, 4] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
Console.WriteLine(m.SearchRowwiseColumnWiseMatrix(mat, 11));
}输出
TRUE
更新于: 17-8-2021
181次浏览
广告