杨氏矩阵
题目：
有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的。
请编写程序在这样的矩阵中查找某个数字是否存在。
要求：时间复杂度小于O(N);
思路：
第一：首先按题目创建一个每行从左到右递增，从上到下是递增的矩阵。
第二：因为时间复杂度小于O(N)，所以不能用两个for循环嵌套。要用一个循环。
第三：我们可以从第0行的最后一位元素开始找， 将要查找值与它比较；
第四：查找值大我们就去下一行找（i++），因为这个值已经是本行最大值了；
第五：查找值小我们就往这行前面找（j - -），因为当前值是本行最大值。找到返回1，未找到返回0.
1. //杨氏矩阵 2. //从左到右递增 3. //从上到下递增 4. #include<stdio.h> 5. 6. int find(int arr[3][3], int row, int col, int key) 7. { 8. int i = 0;//从第0行 9. int j = col - 1;//每一行中最后一个元素，也是最大的元素 10. while (i < row && j >= 0)//条件小于第row行,大于等于第0位 11. { 12. 13. if (key > arr[i][j]) 14. i++;//下一行 15. else if (key < arr[i][j]) 16. j--;//往前找 17. else 18. return 1; 19. 20. } 21. 22. 23. return 0; 24. 25. 26. } 27. 28. int main() 29. { 30. 31. int arr[3][3] = 32. { {1,2,3}, 33. {4,5,6}, 34. {7,8,8} 35. }; 36. 37. int ret = find(arr, 3, 3, 7);//用ret来接受函数的返回值 38. 39. if (ret == 1)//判断结果 40. { 41. printf("find it"); 42. } 43. else 44. { 45. printf("not find"); 46. } 47. 48. 49. return 0; 50. }
