矩阵元素查找

//时间复杂度O(n+logm)

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        for (int i = 0; i < n; i++) {
            if (x >= mat[i][0] && x <= mat[i][m - 1]) {
                int l = 0;
                int r = m - 1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (mat[i][mid] > x) r = mid - 1;
                    else if (mat[i][mid] < x) l = mid + 1;
                    else return new int[]{i, mid};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        for(int i=0;i<n;i++){
            if(mat[i][0]<=x && mat[i][m-1]>=x){
                int p1=0, p2=m-1;
                while(p1<=p2){
                    int mid=(p1+p2)/2;
                    if(mat[i][mid]==x){
                        return new int[]{i,mid};
                    }else if(mat[i][mid]>x){
                        p2=mid-1;
                    }else{
                        p1=mid+1;
                    }
                }
            }
        }
        return null;
    }

 public int[] findElement(int[][] mat, int n, int m, int x) {
        int col = m -1;
        int row = 0;
        while (col>=0 && row<=mat.length-1){
            if (mat[row][col]  == x){
                return  new int[]{row,col};
            }else if (mat[row][col] > x){
                col--;
            }else {
                row++;
            }
        }

        return null;
    }

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // 有序数组
        if (m == 0 || n == 0) return null;
        int i = 0, j = 0;
                // 先确定 列的位置
        for ( ; j < m; ++ j) {
            if (mat[0][j] <= x && x <= mat[n - 1][j]) break;
        }
                // 再确定 行的位置
        for ( ; i < n; ++ i) {
            if (mat[i][j] == x) break;
        }
        int[] res = {i ,j};
        return res;
    }
}

public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int[] res = new int[2];
        int i = 0;
        int j = m-1;
        //从上往下，从右往左比较，x>mat[i][j]则下移一行，x<mat[i][j]则左移一列
        while(i<n&&j>=0){
            if(mat[i][j]>x) j--;
            else if(mat[i][j]<x) i++;
            else{
                res[0]=i;
                res[1]=j;
                break;//一定要返回，否则会死循环
            }
        }
        return res;
    }

* 思路： * 在矩阵中寻找元素，并返回该数的行和列。 * 设lin为行，row为列。 *      1、因为矩阵是有序的，所以我们首先可以拿该元素与每行最后一个元素比较 * 如果比最后一个元素大那肯定在下一行，lin++ *      2、在列中就相当于一元数组进行比较，得到该元素的列。

public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int lin; //行
        int row;//列
        int[] array = new int[2]; //设置结果一维数组。最终将行与列存入该数组。
        //遍历外层数组
        for (lin = 0; lin < n; lin++) {
            if(x > mat[lin][m-1]){
                continue;
            }else{
                //遍历该行的内部数组与m做比较得到列
                for (row = 0; row < m; row++) {
                    //比较大小
                    if(x == mat[lin][row]){
                        array[0] = lin;
                        array[1] = row;
                        break;
                    }
                }
            }
        }
        return array;
    }

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int i = 0;
        int j = m - 1;
        while (i < n && j >= 0) {
            if (mat[i][j] > x) {
                j--;
            } else if (mat[i][j] < x) {
                i++;
            } else {
                break;
            }
        }
        return new int[] {i, j};
    }
}

import java.util.*;
public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        //为了个人的阅读方面，令m代表行，n代表列
        int tmp=n;
        n=m;m=tmp;
        int [] res=new int[2];
        //从右上角开始，如果x大于该数，则下移，若小于则右移
        int i=0,j=n-1;
        while(i<m&&j>=0)
            {
                if(x>mat[i][j])i++;
                else if(x<mat[i][j])j--;
                else{
                    res[0]=i;
                    res[1]=j;
                    break;
                }
            }
            return res;
    }
}

//二维数组中的查找
    public int[] findElement(int[][] mat, int n, int m, int x) {
        //初态在右上角位置 左至右升序 上至下升序 那么这个位置只能左走使得当前数减少和下走使当前数增加
        int row = 0, col = m-1;
        while (col>=0&&row<n){
            if (x>mat[row][col]) row++;//当前数小 要增加只能往下走
            else if (x<mat[row][col]) col--; //当前数太大 要减少只能左走
            else {//不大不小就是相等
                return new int[]{row,col};
            }
        }
        return new int[0];
    }

    //之所以一上来找行不行 是因为输入不是连续的 每一行跟下一行元素完全可以错开 不一定下面全比上面大
    //每一行进行一下二分即可
    public int[] findElement2(int[][] mat, int n, int m, int x) {
        int rowNum = 0, colNum = 0;
        for (int i = 0; i < n; i++) {
            colNum = binarySearch(mat, m, i, x);
            if (colNum != -1) {
                rowNum = i;
                return new int[]{rowNum, colNum};
            }
        }
        return new int[0];

    }

    public int binarySearch(int[][] mat, int m, int rowNum, int x) {
        int left = 0, right = m - 1, colNum = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (x == mat[rowNum][mid]) {
                colNum = mid;
                return colNum;
            } else if (x > mat[rowNum][mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        int[]goal=new int[2];
        int i=n-1,j=0;
        while(i>=0&&j<m){//从下往上，先确定行号，然后再遍历这一行确定列
            if(mat[i][j]==x){
                goal[0]=i;
                goal[1]=j;
                break;
            }
            else if(mat[i][j]>x) i--;
            else j++;//
        }
        return goal;
    }
}

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
    	if (n < 1 || m < 1) {
    		return new int[0];
    	}
    	
    	int row_num = 0;
    	int column_num = m - 1;
    	int[] res = new int[2];
    	
    	while (row_num >= 0 && row_num < n && column_num >= 0 && column_num < m){
    		if (mat[row_num][column_num] == x) {
    			res[0] = row_num;
    			res[1] = column_num;
    			return res;
    		}
    		
    		if (mat[row_num][column_num] > x) {
    			column_num--;
    			continue;
    		}
    		
       		if (mat[row_num][column_num] < x) {
       			row_num++;;
    		}
    		
    	}
    	
    	return new int[0];
    }
}

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        int i=n-1;
        int j=0;
        int[] result=null;
        while(i>=0&&j<=m-1){
            if(x>mat[i][j]){
                j++;
            }else if(x<mat[i][j]){
               i--;
            }else{
                result=new int[2];
                result[0]=i;
                result[1]=j;
                return result;
            }
        }
        return null;
    }
}