在矩阵(二维数组)中查找目标值的坐标

SearchIn2DMatrix.cs

/*
  Q: 给定一个的目标值，在一个横向有序和纵向有序的二维数组（矩阵 matrix）中找到该目标值的坐标


  可以从矩阵的右上角或者左下角开始查找。
  假设从右上角开始查询：
    如果当前元素大于目标值，则可以排除当前元素所在的列，因为这一列都会比目标值大；
    如果当前元素小于目标值，则可以排除当前元素所在的行，因为这一行都会比目标值小。
  通过这种方式，每次都可以排除一整行或者一整列，大大减少了比较的次数，时间复杂度为 O(m+n)
*/
int[,] matrix = new int[,]
{
    { 1, 4, 35, 45, 50 },
    { 5, 26, 39, 49, 57 },
    { 9, 29, 40, 51, 68 },
    { 14, 30, 46, 63, 77 },
    { 21, 37, 52, 80, 91 },
};

foreach (int target in matrix)
{
    Console.WriteLine($"{target}: {string.Join(',', SearchIn2DMatrix(matrix, target))}");
}

/**
 * 对于给定的矩阵，如果我们要查询一个目标值是否存在于该矩阵中，时间复杂度最优的算法应该是 O(log(mn)) 的二分查找算法。
 * 
 * 不过，由于该矩阵本身具有特殊的性质，即每一行都是按照递增顺序排序的，并且每一行的第一个元素都大于前一行的最后一个元素，
 * 每一列也是按照递增顺序排序的，并且每一列的第一个元素都大于前一列的最后一个元素。因此，我们可以利用这些性质来设计一个更加高效的算法。
 * 
 * 具体来说，我们可以从矩阵的右上角或者左下角开始查找。假设我们从右上角开始查找，如果当前元素比目标值大，则我们可以排除当前元素所在的列；
 * 如果当前元素比目标值小，则我们可以排除当前元素所在的行。通过这种方式，每次我们都可以排除一整行或者一整列，从而大大减少了比较的次数，使得时间复杂度可以降至 O(m+n)。
 * 在上述代码中，我们从右上角开始遍历矩阵：
 *  1.如果当前元素等于目标值，则返回该元素的坐标；
 *  2.如果当前元素大于目标值，则说明目标值不可能在当前元素所在的列，因此排除该列，col--；
 *  3.如果当前元素小于目标值，则说明目标值不可能在当前元素所在的行，因此排除该行，row++。
 *  4.最终如果未找到目标值，则返回 null。
 *
 */
int[] SearchIn2DMatrix(int[,] matrix, int target)
{
    int rows = matrix.GetLength(0);
    int cols = matrix.GetLength(1);

    int row = 0;
    int col = cols - 1;

    while (row < rows && col >= 0)
    {
        int curr = matrix[row, col];
        if (curr == target)
        {
            return new int[] { row, col };
        }
        else if (curr > target)
        {
            col--;
        }
        else
        {
            row++;
        }
    }

    return null;
}

// 嵌套循环在矩阵中获取目标值的坐标，时间复杂度O(mn)
//(int row,int col) GetPositionByNestedLoop(int num)
//{
//    var numsOfRow = array.Length;
//    var numsOfColumn = 5;
//    for (int row = 0; row < numsOfRow; row++)
//    {
//        for (int col= 0; col < numsOfColumn; col++)
//        {
//            if (array[row,col] == num)
//            {
//                return (row, col);
//            }
//        }
//    }

//    return (-1, -1);
//}