编程知识 cdmana.com

Yang's matrix number search

{"type":"doc","content":[{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" One background "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" An algorithm problem encountered : We know the elements in the matrix , Each row Increasing from left to right ; Each column Increasing from top to bottom ; Given a number t, It is required to determine whether this element exists in the matrix ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" requirement : The time complexity is as low as possible "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Two Concept "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Such a matrix is also called a young matrix , Usually it can be represented by two-dimensional array ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" An example of Young's matrix (1):"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/ab/ab013df5e72cc370b81a32b2854dd896.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Here's a place to pay attention to , Increment per row and increment per column , There is no guarantee that the number on the right must be greater than the number on the left in case of cross row . We can only know The upper left must be smaller than the lower right ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The reason for describing so much , It's because the answer to this question must be based on the understanding of Young's matrix ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" 3、 ... and Solution and thinking "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3.1 Array traversal "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"m That's ok n Column array , Number by number , The worst time complexity is O(mxn);"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3.2 Traversal optimization -1"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"3.1 The solution does not use any known information . Consider a line of numbers , Increasing from left to right , So we can do that 3.1 On the basis of , Change the search within each row to a binary search , The time complexity is O(m logn)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" If m!=n, Then it can be reduced to O(min(mxlogn,nlogm))"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3.3  Traversal search optimization -2"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The optimization of Young's matrix search : Because young's matrix is gradually increasing from left to right and from top to bottom , If you look for 11 The number of , From the first line, from left to right , If you find something greater than 11 First value of , This shows that this line has no value , Now look down , Look at the value below if it is greater than 11 Look left , If you find something less than 11 First value of , This indicates that there is no value in this line , Now go down and look for , If the value below is less than the value you are looking for, look right , In this way, the target value can be found repeatedly , Compared with traversal search, there is a lot less comparison , But the implementation process is also more complex "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3.4  The recursive method "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" All the elements are scanned and recursively solved . According to the characteristics of Young's matrix, we can find the lower and right sides of the current elements in the matrix every time until the number to be searched key If it is less than the current element, it means that there is no return without this number false, In this way, every time you change the coordinates of the elements to be found and call the method recursively , Until the coordinates of the elements are greater than the length of the two-dimensional array false that will do ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3.5  Divide and conquer to find "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Take the diagonal of the first element in the element , Because of its characteristics, the diagonal elements are also increasing , If there is, it's on the diagonal , If not, find two numbers adjacent to the target value, and then find two possible submatrix through these two numbers . Then go ahead and take the first element of each matrix so that you can find . The specific method to find the adjacent submatrix is :"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" For the smaller value, take the matrix formed by the right and bottom sides . The value in this matrix is greater than it . For the larger value, take the matrix formed by its left and upper edges , The value in the matrix is less than it . Look for the diagonal again and again , Find the rectangle . You can find this value ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":"3.6 Location search "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Compare elements from the right , If it is larger than the target element, look left for comparison , If it's smaller than the target element, go down and move on to the left , This method is compared with 3.3, Fortunately, you don't have to look right , Because the top of the right must be greater than the value to look for, then its right must be greater than the value to look for , This is determined by the properties of Young's matrix ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To simplify the steps , It's better to start from the upper right corner of the matrix ( namely first line The first n-1 Column ) or The lower left corner ( The first m Xing di 0 Column ) Start looking for , This is to make the best use of matrix properties . Take the upper right corner as an example , Here we use the example matrix to illustrate , The element to be found is 10:"}]},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/16/16d93d2b19843251e01fe36b7ffb54bb.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"1、 The element in the upper right corner is 8, Less than 10; and 8 The row is the largest value , So we can only look down ,8 The elements in the first line are excluded ;"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/a0/a0bf4af33bf98e7f57181f84adda98f8.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"2、9 Still less than 10, So keep going down , find out 11>10, So look left in the line ,(11 All the elements in this column can be excluded , Because of the above 8、9 The first two rounds have ruled out , and 11 The following elements are greater than 11, So nature is bigger than 10)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/15/152f71dabbc7907559f4a80564c16a74.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"3、9<10, Because the elements on the right have been excluded , So there's only the next line in the same column ( Elements 10) The only choice "}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/98/98ce7f7cb103dd4291c08c4841859e72.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"4、10 It happens to be the element to look for , So return to success . It is easy to infer that , The worst case scenario is to continue in the last line , Traverse the remaining two elements to the left ."}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The worst time complexity of this method is O(m+n)"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/96/96746f4c8eaaba66fdc0ea37ace24683.png","alt":null,"title":null,"style":null,"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Based on the above analysis and the derivation process shown in the example , You can write the following code 【java edition 】:"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"text"},"content":[{"type":"text","text":"public class YoungSearch {\n \n public static int findNum(int[][] arr, int row, int col, int target){\n int i=0;\n int j=col-1;\n while(i=0){\n if(arr[i][j] < target){\n ++i;\n }\n else if(arr[i][j]>target){\n --j;\n }else{\n return 1;\n }\n }\n return 0;\n }\n \n \n public static void main(String[] args){\n int a[][] = {{ 1, 3, 5 }, { 3, 5, 7 }, { 5, 7, 9 }};\n \n int result = findNum(a, 3,3, 3);\n System.out.println(result);\n }\n}"}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢

Scroll to Top