如何使用 C# 在逐行增加的矩阵中搜索？

Z时代
2024-01-10
分类：综合

这个问题的原始解决方案是扫描输入矩阵中存储的所有元素以搜索给定的键。O(MN)如果矩阵的大小为 MxN，则这种线性搜索方法会花费时间。

矩阵需要从右上角扫描，如果搜索元素大于右上角元素，则增加行或减少列。下面的一段代码开发了一个函数 SearchRowwiseIncrementedMatrix，它将一个二维数组和搜索关键字作为输入，并根据找到的搜索关键字的成功或失败返回真或假。

代码

public class Matrix{
   public bool SearchRowwiseIncrementedMatrix(int[,] mat, int searchElement){
      int row = getMatrixRowSize(mat);
      int col = getMatrixColSize(mat) - 1;
      int r = 0;
      while (col >= 0 && r < row){
         if (mat[r, col] == searchElement){
            return true;
         }
         else if (searchElement < mat[r, col]){
            col--;
         }
         else{
            r++;
         }
      }
      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, 7, 10, 19 }, { 2, 8, 11, 20 }, { 3, 9, 12, 21 } };
   Console.WriteLine(m.SearchRowwiseIncrementedMatrix(mat, 11));
}