題目描述 在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。例如：下麵的二維數組就是每行、每列都遞增排序。如果在這個數組中查找數字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中就可以了。
測試
[Fact] public void Test1() { int[,] array = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } }; int target = 4; Assert.True(Coding001.FindForSimple(array, target)); Assert.True(Coding001.FindForRight(array, target)); } [Fact] public void Test3() { int[,] array = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } }; int target = 3; Assert.False(Coding001.FindForSimple(array, target)); Assert.False(Coding001.FindForRight(array, target)); } [Fact] public void MinTest() { int[,] array = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } }; int target = 0; Assert.False(Coding001.FindForSimple(array, target)); Assert.False(Coding001.FindForRight(array, target)); } [Fact] public void MaxText() { int[,] array = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } }; int target = 16; Assert.False(Coding001.FindForSimple(array, target)); Assert.False(Coding001.FindForRight(array, target)); } [Fact] public void Test5() { int[,] array = { { 1, 2, 3, 4 }, { 2, 3, 4, 5 }, { 3, 4, 5, 6 } }; int target = 3; Assert.True(Coding001.FindForSimple(array, target)); Assert.True(Coding001.FindForRight(array, target)); Assert.True(Coding001.FindForN(array, target)); } [Fact] public void Test6() { int[,] array = { { 1, 2, 3, 4 }, { 2, 3, 4, 5 }, { 3, 4, 5, 6 } }; int target = 7; Assert.False(Coding001.FindForSimple(array, target)); Assert.False(Coding001.FindForRight(array, target)); Assert.False(Coding001.FindForN(array, target)); } [Fact] public void Test7() { int[,] array = { { 1, 3, 5, 7 }, { 3, 5, 7, 9 }, { 5, 7, 9, 11 } }; int target = 9; Assert.True(Coding001.FindForSimple(array, target)); Assert.True(Coding001.FindForRight(array, target)); Assert.True(Coding001.FindForN(array, target)); } [Fact] public void Test8() { int[,] array = { { 1, 3, 5, 7 }, { 3, 5, 7, 9 }, { 5, 7, 9, 11 } }; int target = 8; Assert.False(Coding001.FindForSimple(array, target)); Assert.False(Coding001.FindForRight(array, target)); Assert.False(Coding001.FindForN(array, target)); }View Code
結果
