java - 多维数组的时间复杂度(每次切割成四分之一时)

Question

我们得到一个大小为 NxN 的矩阵，用多维数组表示，矩阵包含整数，我们假设 N=2^K。 我们也可以说矩阵是有序的，方法是将矩阵切割成 4 个四分之一(下图)，第一个四分之一的每个元素都小于或等于第二个四分之一的元素，第二个季度小于或等于第三个季度，第三个季度中的每个元素都小于或等于第四个季度中的每个元素。 (递归地依此类推)

像这样:

1 2
3 4

排序矩阵的例子:

我们需要编写一个函数，如果矩阵中存在 num 则返回 true。 并使其尽可能高效。

我编写了以下函数:

public static boolean isExist(int[][] mat, int num)
{
    int start_rows = 0; 
    int start_columns = 0; 

    // If more then 4 elements
    // Loop log(base 4)n
    for (int elements_size = mat.length * mat[0].length, table_size, quarter_size,
            quarter1, quarter2, quarter3, quarter4; 
            (elements_size > 4); 
            elements_size /= 4) 
    {
        table_size = (int)(Math.sqrt(elements_size));
        quarter1 = mat[start_rows+(table_size/2)-1][start_columns+(table_size/2)-1];
        quarter2 = mat[start_rows+(table_size/2)-1][start_columns+table_size-1];
        quarter3 = mat[start_rows+table_size-1][start_columns+(table_size/2)-1];
        quarter4 = mat[start_rows+table_size-1][start_columns+table_size-1];

        if (num == quarter1 || num == quarter2 || num == quarter3 || num == quarter4) {
            return true;
        }

        // Decrease elements_size
        quarter_size = (int)Math.sqrt(elements_size/4);

        if (quarter1 > num) {
            // Dont do anything
        } else if (quarter2 > num) {
            start_columns += quarter_size;  // Increase columns
        } else if (quarter3 > num) {
            start_rows += quarter_size; // Increase rows
        } else if (quarter4 > num) {
            start_rows += quarter_size; // Increase rows
            start_columns += quarter_size; // Increase columns
        } else {
            return false; // bigger then quarter, fail.
        }
    }

    return (mat[start_rows][start_columns] == num || mat[start_rows+1][start_columns] == num || 
            mat[start_rows][start_columns+1] == num || mat[start_rows+1][start_columns+1] == num);
}

这是最有效的方法吗？ 它的时间复杂度也是 O(logn)。 (我说得对吗？)

Answer 1

嗯，这是个好方法! 如果我没理解错的话，你想知道数组是否包含特定的 int 值； 好吧，我会使用以下方法(但你必须将其与 int [][] 数组相匹配):

HashSet<Integer> test= new HashSet<Integer>(Arrays.asList(intArray));
test.contains(intValue)

这种方法非常快，因为哈希码机制的复杂度为 O(1)，但我认为通过 asList()- 它会导致数组列表的复杂度为 O(n)...对此我不确定!!