网站模版,怎么用ps做网站首页背景图片,微信企业邮箱登录入口,导航类wordpress主题1. 设查找的数位y#xff0c;第一行最后一列的数位x 如果xy#xff0c;x是第一行最大的#xff0c;所以第一行都小于y#xff0c;删除第一行#xff1b; 如果xy#xff0c;x是最后一列最小的#xff0c;所以最后一列都大于y#xff0c;删除最后一列#xff1b…1. 设查找的数位y第一行最后一列的数位x 如果xyx是第一行最大的所以第一行都小于y删除第一行 如果xyx是最后一列最小的所以最后一列都大于y删除最后一列 这样保证x永远在可能有解的矩阵的第一行最后一列。 时间复杂度Omn 1 class Solution {2 public:3 /**4 * param matrix, a list of lists of integers5 * param target, an integer6 * return a boolean, indicate whether matrix contains target7 */8 bool searchMatrix(vectorvectorint matrix, int target) {9 // write your code here
10 int m matrix.size();
11 if (m 0) {
12 return false;
13 }
14 int n matrix[0].size();
15 int r 0, c n - 1;
16 while (r m c 0) {
17 if (matrix[r][c] target) {
18 r;
19 } else if (matrix[r][c] target) {
20 c--;
21 } else {
22 return true;
23 }
24 }
25 return false;
26 }
27 }; 2. 分治法1 设查找的数位y取中心点x把矩阵分解成4部分 如果xyx是A中最大的所以A都小于y删除A 如果xyx是D中最小的所以D都小于y删除D A B ———— C D 时间复杂度O(N) O(N/4)O(N/2)O(1), 介于O(N^0.5)~O(N)之间 1 class Solution {2 public:3 /**4 * param matrix, a list of lists of integers5 * param target, an integer6 * return a boolean, indicate whether matrix contains target7 */8 bool helper(vectorvectorint M, int x1, int y1, int x2, int y2, int target) {9 if (x1 x2 || y1 y2) {//empty matrix
10 return false;
11 }
12 int midx (x1 x2)1;
13 int midy (y1 y2)1;
14 if (M[midx][midy] target) {
15 return true;
16 }
17 return (M[midx][midy] target)?
18 (helper(M, x1, y1, x2, midy-1, target)||helper(M, x1, midy, midx-1, y2, target)):
19 (helper(M, x1, midy1, x2, y2, target)||helper(M, midx1, y1, x2, midy, target));
20
21 }
22 bool searchMatrix(vectorvectorint matrix, int target) {
23 // write your code here
24 int m matrix.size();
25 if (m 0) {
26 return false;
27 }
28 int n matrix[0].size();
29 return helper(matrix, 0, 0, m - 1, n - 1, target);
30 }
31 }; 3. 分治法2 设查找的数为y在中线找到这样两个数x1x2使得x1y,x2y把矩阵分成4部分 A B ———— C D x1是A中最大的所以A都小于y删掉A x2是D中最小的所以D都大于y删掉D 时间复杂度O(N)2O(N/4)O(logn), 为O(N^0.5) 1 class Solution {2 public:3 /**4 * param A, a list of integers5 * param left, an integer6 * param right, an integer7 * param target, an integer8 * return an integer, indicate the index of the last number less than or equal to target in A9 */
10 int binarySearch(vectorint A, int left, int right, int target) {
11 while (left right) {//not an empty list
12 int mid (left right) 1;
13 if (A[mid] target) {
14 left mid 1;//left is in the integer after the last integer less than or equal to target
15 } else {
16 right mid - 1;
17 }
18 }
19 return left - 1;
20 }
21 /**
22 * param M, a list of lists of integers
23 * param x1, an integer
24 * param y1, an integer
25 * param x2, an integer
26 * param y2, an integer
27 * param target, an integer
28 * return a boolean, indicate whether matrix contains target
29 */
30 bool helper(vectorvectorint M, int x1, int y1, int x2, int y2, int target) {
31 if (x1 x2 || y1 y2) {//empty matrix
32 return false;
33 }
34 int midx (x1 x2)1;
35 int indy binarySearch(M[midx], y1, y2, target);
36 //M[midx][indy] target
37 if ((indy y1) (M[midx][indy] target)) {
38 return true;
39 }
40 return (helper(M, x1, indy1, midx-1, y2, target))||(helper(M, midx1, y1, x2, indy, target));
41
42 }
43 /**
44 * param matrix, a list of lists of integers
45 * param target, an integer
46 * return a boolean, indicate whether matrix contains target
47 */
48 bool searchMatrix(vectorvectorint matrix, int target) {
49 // write your code here
50 int m matrix.size();
51 if (m 0) {
52 return false;
53 }
54 int n matrix[0].size();
55 return helper(matrix, 0, 0, m - 1, n - 1, target);
56 }
57 };
