floor

fiei3ece  于 2021-09-13  发布在  Java
关注(0)|答案(1)|浏览(302)

我有一个排序数组 arr[] 大小 n 没有重复项,并且给定了一个值 x . 地板 x 定义为中的最大元素k arr[] 使得k小于或等于 x . 查找k的索引(基于0的索引)。
输入:

n = 7
x = 0
arr[] = {1,2,8,10,11,12,19}

输出:

1

我必须在o(logn)中解决它。下面的代码通过了测试用例,但它显示超出了时间限制。这个代码有什么问题?

static int findFloor(long arr[], int n, long x) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] > x) {
            if (mid != 0 && arr[mid - 1] < x) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else if (arr[mid] < x) {
            low = mid + 1;
        }
    }
    return -1;
}
h43kikqp

h43kikqp1#

在这种情况下,您的程序将陷入无限状态 arr[mid] == x 因为你没有处理过这个案子。另外,我不认为这个程序在其他情况下也能正常工作。
例如,如果我给 x=7 ,这将返回索引 2 ,这是错误的。正确的索引应该是 1 作为 x=7arr[1] == 2 不到 arr[2] == 8 .
另外,如果我输入的值大于数组中的最后一个元素,比如 x=50 在你的例子中。你会得到一份工作的 ArrayIndexOutOfBoundException 作为你的 low 将增加并使 mid 索引越界。
我已经纠正了上述情况,修复函数如下所示:

static int findFloor(long[] arr, int n, long x) {
    if (x >= arr[arr.length - 1]) {
        return arr.length - 1;
    }
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] > x) {
            if (mid != 0 && arr[mid - 1] < x) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            if (arr[mid] == x || (mid != 0 && arr[mid + 1] > x)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

希望你得到你的答案。

相关问题