题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如：下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字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 == )
{
int rowLength = array.GetLength();
int colLength = array.GetLength();
int start = array[, ];
int end = array[rowLength - , colLength - ];
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();
int colLength = array.GetLength(); int row = , col = colLength - ;//坐标右上角
while (row < rowLength && col >= )
{
if (array[row, col] == target)
{
result = true;
break;
}
else if (array[row, col] > target)
{
col--;
}
else
{
row++;
}
}
} return result;
}
想入非非：扩展思维，发挥想象
目的：
1. 熟悉二维数组
2. 不要动不动就循环，多想想
扩展：
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();
int colLength = array.GetLength();
int first = array[, ];
int second = ; if (rowLength > ) { second = array[, ]; }
else if (colLength > ) { second = array[, ]; }
else { second = target; } int n = second - first;
if (n == )
{
if (first == target)
{
result = true;
}
}
else
{
int remainder = (target - first) % n;
if (remainder == )
{
result = true;
}
}
} return result;
}
2. 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数，有返回数据的坐标
解题思路：按照右上角的解题思路，把坐标记录放到list中就可以了。
测试
[Fact]
public void Test1()
{
int[,] array = { { , , , }, { , , , }, { , , , }, { , , , } };
int target = ;
Assert.True(Coding001.FindForSimple(array, target));
Assert.True(Coding001.FindForRight(array, target));
} [Fact]
public void Test3()
{
int[,] array = { { , , , }, { , , , }, { , , , }, { , , , } };
int target = ;
Assert.False(Coding001.FindForSimple(array, target));
Assert.False(Coding001.FindForRight(array, target));
} [Fact]
public void MinTest()
{
int[,] array = { { , , , }, { , , , }, { , , , }, { , , , } };
int target = ;
Assert.False(Coding001.FindForSimple(array, target));
Assert.False(Coding001.FindForRight(array, target));
} [Fact]
public void MaxText()
{
int[,] array = { { , , , }, { , , , }, { , , , }, { , , , } };
int target = ;
Assert.False(Coding001.FindForSimple(array, target));
Assert.False(Coding001.FindForRight(array, target));
} [Fact]
public void Test5()
{
int[,] array = { { , , , }, { , , , }, { , , , } };
int target = ;
Assert.True(Coding001.FindForSimple(array, target));
Assert.True(Coding001.FindForRight(array, target));
Assert.True(Coding001.FindForN(array, target));
} [Fact]
public void Test6()
{
int[,] array = { { , , , }, { , , , }, { , , , } };
int target = ;
Assert.False(Coding001.FindForSimple(array, target));
Assert.False(Coding001.FindForRight(array, target));
Assert.False(Coding001.FindForN(array, target));
} [Fact]
public void Test7()
{
int[,] array = { { , , , }, { , , , }, { , , , } };
int target = ;
Assert.True(Coding001.FindForSimple(array, target));
Assert.True(Coding001.FindForRight(array, target));
Assert.True(Coding001.FindForN(array, target));
} [Fact]
public void Test8()
{
int[,] array = { { , , , }, { , , , }, { , , , } };
int target = ;
Assert.False(Coding001.FindForSimple(array, target));
Assert.False(Coding001.FindForRight(array, target));
Assert.False(Coding001.FindForN(array, target));
}