欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C#版剑指Offer-001二维数组中的查找

程序员文章站 2023-11-12 08:30:22
题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。例如:下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找 ......

题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如:下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。

解题思路

看到该题目想到的最简单暴力做的做法就是直接遍历数组查找。但是实际上一般都要用效率更高的做法,该题目有两个重要条件,从左到右递增,从上到下递增,也就是说每一个数都比前一个大比后一个小,比上面的大比下面的小。由此想到可以右上角或者左下角开始处理,这样每次处理都会剔除一行或者一列,逐渐缩小范围,直到找到要查找的数字或者没有。

代码实现

/// <summary>
/// 检测是否在数组范围内
/// </summary>
/// <param name="array"></param>
/// <param name="target"></param>
/// <returns></returns>
private static bool checkisarrayrange(int[,] array, int target)
{
    bool result = false;
    if (array != null && array.rank == 2)
    {
        int rowlength = array.getlength(0);
        int collength = array.getlength(1);
        int start = array[0, 0];
        int end = array[rowlength - 1, collength - 1];
        if (start <= target && target <= end)
        {
            result = true;
        }
    }
    return result;
}

/// <summary>
/// 暴力解法-直接遍历
/// </summary>
/// <param name="array">数组</param>
/// <param name="target">目标</param>
/// <returns></returns>
private static bool findforsimple(int[,] array, int target)
{
    bool result = false;
    if (checkisarrayrange(array, target))
    {
        foreach (var item in array)
        {
            if (target == item)
            {
                result = true;
                break;
            }
        }
    }
    return result;
}

/// <summary>
/// 右上角解题
/// </summary>
/// <param name="array"></param>
/// <param name="target"></param>
/// <returns></returns>
private static bool findforright(int[,] array, int target)
{
    bool result = false;

    if (checkisarrayrange(array, target))
    {
        int rowlength = array.getlength(0);
        int collength = array.getlength(1);

        int row = 0, col = collength - 1;//坐标右上角
        while (row < rowlength && col >= 0)
        {
            if (array[row, col] == target)
            {
                result = true;
                break;
            }
            else if (array[row, col] > target)
            {
                col--;
            }
            else
            {
                row++;
            }
        }
    }

    return result;
}

想入非非:扩展思维,发挥想象

1. 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增n的顺序排序,每一列都按照从上到下递增n的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解题思路:从左到右递增n,从上到下递增n,这属于等比递增数组(自己起的),这样的如果还用右上角的做法,那效率不是很高,正确的做法是用等比数列计算求值的方法。(target-start)/n,如果可以整除,那么这个数据就存在,不能整除就不存在。

代码实现

/// <summary>
/// 等比数列的数组
/// </summary>
/// <param name="array"></param>
/// <param name="target"></param>
/// <returns></returns>
private static bool findforn(int[,] array, int target)
{
    bool result = false;
    if (checkisarrayrange(array, target))
    {
        int rowlength = array.getlength(0);
        int collength = array.getlength(1);
        int first = array[0, 0];
        int second = 0;

        if (rowlength > 1) { second = array[1, 0]; }
        else if (collength > 1) { second = array[0, 1]; }
        else { second = target; }

        int n = second - first;
        if (n == 0)
        {
            if (first == target)
            {
                result = true;
            }
        }
        else
        {
            int remainder = (target - first) % n;
            if (remainder == 0)
            {
                result = true;
            }
        }
    }

    return result;
}

2. 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数,有返回数据的坐标
解题思路:按照右上角的解题思路,把坐标记录放到list中就可以了。

测试

//int[,] array = { { 1, 2, 3, 4 }, { 2, 3, 4, 5 }, { 3, 4, 5, 6 } };
//int[,] array = { { 1, 3, 5, 7 }, { 3, 5, 7, 9 }, { 5, 7, 9, 11 } };
int[,] array = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
int target = 4;
console.writeline($"{findforsimple(array, target)},{findforright(array, target)}");