Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1384
Question Name: Find an Integer in 2D Array
Question Description: in a 2D array, independently every row/column is already sorted in ascending order. Given a such 2D array and an integer, write a function to check whether the array contains that integer.
Input: there may be multiple test cases per execution. In each test case, the first line contains two integers m and n (1<=m,n<=1000), to indicate the number of rows and columns in the array respectively. The second line is an integer to be found in the array. The following m lines contain n integers in each, as the content of the matrix.
Output: print “Yes” if the matrix contains the integer, or “No” otherwise.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | Input: 3 3 5 1 2 3 4 5 6 7 8 9 3 3 1 2 3 4 5 6 7 8 9 10 3 3 12 2 3 4 5 6 7 8 9 10 Output: Yes No No |
To solve it, we could use a method, simiar with binary search.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | /** * Filename : FindIn2DArray.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-07-30 * JDK used : 1.7 * Changelog : None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class FindIn2DArray { /** * From the stdin, get a 2D array and a number. Check whether * the number is in the array. * @exception IOException: if error happens in reading from stdin. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int row, column; // Record the number of rows and columns. int toFind; // The number to find in the 2D array. FindIn2DArray finder = new FindIn2DArray(); // For test usage. while (st.nextToken() != StreamTokenizer.TT_EOF) { // Starting a new test case. // Read the number of rows in this case. row = (int)st.nval; st.nextToken(); // Read the number of columns. column = (int)st.nval; st.nextToken(); // Read the number to find. toFind = (int)st.nval; // Read the test 2D array. int [][] matrix = new int[row][column]; for (int i = 0; i < row; ++i) { for (int j = 0; j < column; ++j) { st.nextToken(); matrix[i][j] = (int)st.nval; } } // Check whether the number is in the 2D array. if (finder.findIn2DArray(matrix, 0, row-1, 0, column-1, toFind)) { System.out.println("Yes"); } else { System.out.println("No"); } } } /** * Searches for the integer in the row-sorted and column-sorted 2D array matrix. * @param matrix : a 2D array. * @param rowBegin : the begin row (inclusive) of matrix to search. * @param rowEnd : the end row (inclusive) of matrix to search. * @param columnBegin : the begin column (inclusive) of matrix to search. * @param columnEnd : the end column (inclusive) of matrix to search. * @param toFind : an integer to find inside matrix. * @return a boolean : true if toFind is in matrix; false otherwise. */ private boolean findIn2DArray(int[][] matrix, int rowBegin, int rowEnd, int columnBegin, int columnEnd, int toFind) { // Terminate case for this recursive function. Did not find toFind yet. if (rowBegin > rowEnd) return false; if (columnBegin > columnEnd) return false; // The middle point of this 2D array. int midRow = (rowBegin + rowEnd) / 2; int midColumn = (columnBegin + columnEnd) / 2; if (matrix[midRow][midColumn] == toFind) { // Find it! return true; } else if (matrix[midRow][midColumn] > toFind) { // If we divide the matrix with the midRow and midColumn into four pieces, // toFind is impossible to be in the lower right sub-matrix. // Try to find toFind in the upper left and lower left sub-matrix. if (findIn2DArray(matrix, rowBegin, rowEnd, columnBegin, midColumn-1, toFind)) { return true; } // Try to find toFind in the upper right sub-matrix. if (findIn2DArray(matrix, rowBegin, midRow-1, midColumn, columnEnd, toFind)) { return true; } return false; } else { // If we divide the matrix with the midRow and midColumn into four pieces, // toFind is impossible to be in the upper left sub-matrix. // Try to find toFind in the lower left and lower right sub-matrix. if (findIn2DArray(matrix, midRow+1, rowEnd, columnBegin, columnEnd, toFind)) { return true; } // Try to find toFind in the upper right sub-matrix. if (findIn2DArray(matrix, rowBegin, midRow, midColumn+1, columnEnd, toFind)) { return true; } return false; } } } |