import java.util.*; import java.io.*; public class TwoDArray { // setup variable stdin to read from standard input private static BufferedReader stdin = new BufferedReader( new InputStreamReader(System.in)); // 1st dimension = computed keys, 2nd = values from which key was derived public static int[][] data; // Number of keys in each slot. Can be thought of as (# of "collisions") + 1 public static int[] sizes; /** * Sets up the data structure by assigning initial dimensions and values. */ public static void initialize() { data = new int[1000][10]; sizes = new int[1000]; for (int i = 0; i < 1000; i++) sizes[i] = 0; } /** * Inserts an arbitrary number into an array, using a simple function * of the number to compute its index. * * @param number - The number on which our key will be based */ public static void insert(int number) { // compute our index (also referred to as a key, or hash, in this case) int location = (number - 1) / 1000; // if the subarray at this location has filled up, then we double its size. if (data[location].length == sizes[location]) { int[] temp; temp = new int[sizes[location] * 2 + 1]; for (int i = 0; i < sizes[location]; i++) temp[i] = data[location][i]; data[location] = temp; } // remember our number by putting it in the next slot data[location][sizes[location]] = number; sizes[location]++; } /** * Searches a 2D array for a given number by computing a key from * the number, and searching the corresponding sub-array at that index. * * @param data - the 2D array to be searched * @param sizes - the supplemental "number of inserts" array * @param number - The number which may have been previously inserted * @return An integer representing the order in which the number * was originally inserted, or -1, if the number was not found. */ public static int search(int[][] data, int[] sizes, int number) { // compute our location key from the input number int location = (number - 1) / 1000; // search the 2D array at location for (int i = 0; i < sizes[location]; i++) // if we've found our number, return its location if (number == data[location][i]) return i; return -1; } public static void main(String[] args) { // Initialize structure initialize(); // read and insert until no more numbers while (true) { // Prompt the user System.out.println("Type a number you want to insert. "); System.out.print("The number should be in the range 1..1000000: "); try { // Read a line of text from the user. String input = stdin.readLine(); // converts a String into an int value int number = Integer.parseInt(input); if (number <= 0) break; // insert the number into data insert(number); } catch (java.io.IOException e) { System.out.println(e); } } // read and search until no more numbers while (true) { // Prompt the user System.out.println("Type a number you want to search for. "); System.out.print("The number should be in the range 1..1000000: "); try { // Read a line of text from the user. String input = stdin.readLine(); // converts a String into an int value int number = Integer.parseInt(input); if (number <= 0) break; // search for the number into data int column = search(data, sizes, number); if (column >= 0) { System.out.println("row " + (number - 1) / 1000); System.out.println("column " + column); } else System.out.println("Number not found."); } catch (java.io.IOException e) { System.out.println(e); } } } }