时间戳

首页 > 解决方案 > 搜索 2D 排序矩阵部分，如果我在 O(n) 上进行，需要进行代码审查

java - 搜索 2D 排序矩阵部分，如果我在 O(n) 上进行，需要进行代码审查

问题描述

我们有一个任务：

“编写一个高效的算法，在 nxn 表（二维数组）中搜索一个值。这个表是按行和列排序的——即 Table[i][j] ≤ Table[i][j + 1 ], 表[i][j] ≤ 表[i + 1][j]"

如果有人可以查看我的代码并查看我是否在 O(n)，或者我可以使我的代码更有效率。谢谢。

public static boolean find(int [][]a, int x)  // Efficiency O(n)
{

    if(a.length == 0 || a.length != a[0].length) // check if the matrix is squared or empty
        return false;


    int row = 0, col = a.length-1; // setting coordinates

    while(row < a.length && col >= 0) // running while the coordinates in bounce 
    {
        if (x > a[row][col])    // the "x" is bigger then my current spot, go down 1 row
            row++;
        else if(x < a[row][col])    // // the "x" is smaller then my current spot, go back 1 col
            col--;
        else
            return true;    
    }
    return false;

标签： javaalgorithmperformance

解决方案

这是我的粗略草图，但它可以改善您的搜索。我尝试从二维数组进行二进制搜索。希望能帮助到你

static int moves = 0;

public static boolean find1(int[][] a, int x) // Efficiency O(n)
{

    if (a.length == 0 || a.length != a[0].length) // check if the matrix is squared or empty
        return false;

    int row = 0, col = a.length - 1; // setting coordinates

    while (row < a.length && col >= 0) // running while the coordinates in bounce
    {
        moves++;
        if (x > a[row][col]) // the "x" is bigger then my current spot, go down 1 row
            row++;
        else if (x < a[row][col]) // // the "x" is smaller then my current spot, go back 1 col
            col--;
        else
            return true;
    }
    return false;
}

public static boolean find(int[][] a, int x) // Efficiency O(n)
{

    int row = findRow(a, x);
    print(row);
    if (row < 0)
        return false;
    int col = findCol(a[row], x);
    print(col);
    if (col < 0)
        return false;
    return true;
}

public static int findRow(int[][] a, int x) {
    int row = a.length;
    int start = 0, end = a.length - 1;
    while (start <= end) {
        moves++;
        int current = start + (end - start) / 2;
        if (a[current][0] <= x && a[current][a[current].length - 1] >= x) {
            return current;
        } else if (a[current][a[current].length - 1] < x) {
            start = current + 1;
        } else {
            end = current - 1;
        }
    }
    return -1;
}

public static int findCol(int[] a, int x) {
    int start = 0, end = a.length - 1;
    while (start <= end) {
        moves++;
        int current = start + (end - start) / 2;
        if (a[current] == x)
            return current;
        if (a[current] < x)
            start = current + 1;
        else
            end = current - 1;
    }
    return -1;
}

public static void main(String[] args) throws Exception {
    int[][] a = { { 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 } };
    print(find(a, 21));
    print(moves);
    moves = 0;
    print(find1(a, 21));
    print(moves);
}

打印函数只是 System.out.println()，我只是懒惰 ;)

推荐阅读