给定如下的n*n的数字矩阵,每行从左到右是严格递增, 每列的数据也是严格递增
1 2 3
3 5 6
4 8 9
现在要求设计一个算法, 给定一个数k 判断出k是否在这个矩阵中。描述算法并且给出时间复杂度(不考虑载入矩阵的消耗)
public boolean BinaryTreeSearch(int data[][],int k) { if(data==null || data.length==0)return false; int n=data.length; int i=0,j=n-1; while(i<n && j>=0 && data[i][j]!=k) { if(k>data[i][j]) { i++; } else { j--; } } if(i<n && j>=0 && data[i][j]==k)return true; else return false; }
public class Main2 { public static void main(String [] args){ //假设n为8 int n=8; int k=64; int content=0; Integer[] [] nums=new Integer[8][8]; for (int i = 0; i <n; i++) { for (int j = 0; j < n; j++) { nums[i][j]=content++; } } Integer [] first=first(nums,k); if(first==null){ System.out.println(false); }else if(first.length==1){ System.out.println(true); }else{ System.out.println(second(first,k)); } } public static Integer [] first(Integer [][] nums,int k){ if(nums.length==1){ Integer max=nums[0][nums[0].length-1]; Integer min=nums[0][0]; if(k>min&&k<max) return nums[0].clone(); else return null; } int mid=nums.length/2; Integer[] midNums=nums[mid]; if(k<midNums[midNums.length-1]){ return first(Arrays.copyOfRange(nums,0,mid),k); }else if(k>midNums[midNums.length-1]){ return first(Arrays.copyOfRange(nums,mid,nums.length),k); }else{ return new Integer[]{k}; } } public static boolean second(Integer[] first,int k){ if(first.length==1){ return first[0]==k; } int mid=first.length/2; if(k<first[mid]){ return second(Arrays.copyOfRange(first,0,mid),k); }else if(k>first[mid]){ return second(Arrays.copyOfRange(first,mid,first.length),k); }else{ return true; } } }
package Interview; import java.util.Scanner; public class FindKinAMatrix { public static void main(String[] args) { int[][] myArr = inputMatrix(); System.out.println(find(5, myArr)); } static boolean find(int k, int[][] arr) { // 以矩阵的最左下角的元素为基准,若k大于基准值,则往右边走,若k小于基准值,则往上边走 // 先求出矩阵的大小 int row = arr.length; int row_pivot = row - 1; int column_pivot = 0; // 则基准数值为arr[row_pivot][column_pivot] boolean flag = true; //表示在矩阵中没有找到k while (flag && (row_pivot >= 0) && (column_pivot < row)) { if (k > arr[row_pivot][column_pivot]) { column_pivot++; } else if (k < arr[row_pivot][column_pivot]) { row_pivot--; } else { flag = false; // 表示找到了k,退出循环 //System.out.print("k的行数为"+(row_pivot+1)+",列数为"+(column_pivot+1)); break; } } return (!flag); } static int[][] inputMatrix() { // 输入矩阵 Scanner sc = new Scanner(System.in); // 输入第一行数据 String[] firstline = sc.nextLine().split(" "); // 判断矩阵的大小 int n = firstline.length; // 创建一个二位数组,存储输入的数据 int[][] arr = new int[n][n]; for (int i = 0; i < n; i++) { arr[0][i] = Integer.valueOf(firstline[i]); } // 矩阵的第一行数据存储完毕 // 现在输入矩阵的其他行数据 for (int i = 1; i < n; i++) { String[] inputStr = (new Scanner(System.in)).nextLine().split(" "); for (int j = 0; j < n; j++) { arr[i][j] = Integer.valueOf(inputStr[j]); } } return arr; } }
public class test{ int[] arr; private boolean find(int target,int capacity){ arr = new int[capacity * capacity]; for( int n = 0 ; n < capacity ; n ++ ) arr[n] = n + 1; return findImpl(arr,target); } //二分查找 private boolean findImpl(int[] arr,int target){ int higth = arr.length; int low = 0; int mid = (higth + low)/2 while(low < higth){ if(arr[mid] > target){ low = mid + 1; } if(arr[mid] < target){ rigth = mid - 1; } if(arr[mid] == target) return true; mid = (higth + low)/2 } return false; } public stati void main(String[] args){ int num = 0; int capacity = 0;Scanner in = new Scanner(System.in); System.out.println("输入目标数值:"); num = in.nextInt();System.out.println("输入容量:");capacity = in,nextInt();
System.out.println(find(num,capacity));
}
}
public class Test5 { public static void main(String[] args) { int[][] data = {{1,2,3,4,5}, {2,3,4,5,6}, {4,6,7,9,11}, {6,7,11,12,14}, {8,10,12,13,15}}; int number = 16; searchKey(data, number); } private static void searchKey(int[][] arr,int number) { int m = arr.length; int n = arr[0].length; for(int i=m-1,j=0;i>=0 && j<n;) { if(arr[i][j] == number) { System.out.println(true); return; }else if(arr[i][j] < number) { j++; }else { i--; } } System.out.println(false); } }