2

如何从给定的数字数组中找到给定数字的前任？例如，如果给定数组包含 -2,1,0,3
且输入数字为0，则前驱为-2。

我写了以下代码：

public static int getPredecessor(int[] inpArr, int key) {
    int minDiff = key<=0 ? (key-inpArr[0]) : key;
    int predecessor = key;
    for(int i=0;i<inpArr.length;i++) {
        if(inpArr[i] < key && (key - inpArr[i])<=minDiff)
        {
            minDiff = key - inpArr[i];
            predecessor = inpArr[i];
        }   
    }
    return predecessor;
}

我所做的基本上是跟踪提供的数字与数组中每个数字之间的最小差异；每当遇到最小差异时，数组中的那个特定数字就被存储为前任。如果最终的 return 语句将返回与输入数字相同的数字，那么这意味着在给定的数组中没有找到前任。

我的问题是：
可以以任何方式优化代码吗？它以 O(n) 时间和 O(1) 空间复杂度运行。

4

2 回答 2

2

对于未排序数组的单个查询（如示例数组），O(N) 时间是可以实现的最佳时间，因为不可避免地必须与数组中的每个元素进行比较。

首先对数组进行排序将花费 O(N log N) 时间，但是，如果需要对数组进行许多查询，则每个查询都可以通过二进制搜索在 O(log N) 时间内完成。因此，如果有足够的查询，查询的平均成本可能低于 O(N)。

或者，如果期望许多查询使用相同的小（ish）键值集，则使用例如哈希表来记忆每个键的结果，最终将在每次查询时提供平均 O(1) 性能O(N) 空间的成本。

于 2013-02-15T02:38:01.780 回答
0

上面的代码不适用于 inpArr=[-5,-2] 和 key=-4, inpArr=[-5,-2,-3], key=+1 等情况。于是改正了。这是更正后的代码。

public static int getPredecessorv2(int[] inpArr, int key) {
    int minDiff = Math.abs(key);
    int pred = key;
    if(inpArr[0] < key) {
        minDiff = key - inpArr[0];
        pred = inpArr[0];
    } 
    for(int i=0;i<inpArr.length;i++) {
        if(inpArr[i] < key && (key - inpArr[i])<=minDiff)
        {
            minDiff = key - inpArr[i];
            pred = inpArr[i];
        }   
    }
    return pred;
}
于 2013-02-23T20:38:05.610 回答