32

给定一个整数数组，找到局部最小值。如果 A[i-1] > A[i] 且 A[i] < A[i+1] 其中 i = 1...n-2，则元素 A[i] 被定义为局部最小值。在边界元素的情况下，数字必须小于其相邻数字。

我知道如果只有一个局部最小值，那么我们可以通过修改后的二进制搜索来解决。但如果已知数组中存在多个局部最小值，能否及时求解O(log n)？

4

7 回答 7

66

如果不能保证数组元素是不同的，那么就不可能在 O(log n) 时间内做到这一点。原因如下：假设您有一个数组，其中所有 n > 1 值都相同。在这种情况下，没有一个元素可以是局部最小值，因为没有一个元素小于它的邻居。但是，为了确定所有值都相同，您必须查看所有数组元素，这需要 O(n) 时间。如果您使用的时间少于 O(n)，则不一定能查看所有数组元素。

另一方面，如果保证数组元素是不同的，则可以使用以下观察在 O(log n) 时间内解决此问题：

  1. 如果只有一个元素，则保证为局部最小值。
  2. 如果有多个元素，请查看中间元素。如果它是局部最小值，那么您就完成了。否则，它旁边的至少一个元素必须小于它。现在，想象一下，如果您从较小的元素之一开始，并沿着远离中间元素的方向逐渐向数组的一端移动，会发生什么情况。在每一步，要么下一个元素小于前一个元素，要么它会更大。最终，您要么以这种方式达到数组的末尾，要么达到局部最小值。请注意，这意味着您可以这样做是为了找到一个局部最小值。但是，我们实际上不会这样做。相反，我们将使用在数组的这一半中存在局部最小值这一事实作为丢弃一半数组的理由。在剩下的部分中，我们保证找到一个局部最小值。

因此，您可以构建以下递归算法：

  1. 如果只有一个数组元素，则为局部最小值。
  2. 如果有两个数组元素，请检查每个元素。一个必须是局部最小值。
  3. 否则，请查看数组的中间元素。如果是局部最小值，则返回它。否则，至少有一个相邻值必须小于这个值。递归包含该较小元素的数组的一半（但不是中间）。

请注意，这具有递归关系

T(1) ≤ 1

T(2) ≤ 1

T(n) ≤ T(n / 2) + 1

使用主定理，您可以根据需要证明该算法在 O(log n) 时间内运行。

希望这可以帮助！

另请注意，仅当数组的边缘小于相邻元素时，该算法才有效。

于 2012-09-02T17:49:32.490 回答
7

局部最小值的数量可以是n/2; 您无法及时枚举它们O(log n)。

于 2012-09-02T17:44:45.143 回答
6

使用分而治之的算法。令 m = n/2，并检查值 A[m]（即数组中间的元素）。

情况 1：A[m-1] < A[m]。那么数组的左半部分必须包含一个局部最小值，所以在左半部分递归。我们可以通过矛盾来证明这一点：假设 A[i] 不是每个 0 ≤ i < m 的局部最小值。那么 A[m-1] 不是局部最小值，这意味着 A[m-2] < A[m-1]。类似地，A[m -3] < A[m -2]。以这种方式继续，我们得到 A[0] < A[1]。但是 A[0] 是一个局部最小值，这与我们最初的假设相反。

情况 2：A[m + 1] > A[m]。那么数组的右半部分必须包含一个局部最小值，所以在右半部分递归。这与案例 1 对称。

情况 3：A[m - 1] > A[m] 和 A[m + 1] < A[m]。那么 A[m] 是一个局部最小值，所以返回它。运行时间递归为 T(n) = T(n/2) + Θ(1)，得出 T(n) = Θ(log n)。

于 2014-01-20T17:33:50.963 回答
1

你的算法不适用于这个数组

15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1

这里的局部最小值是 12.. 但是当我检查中间元素 7 时，您的算法将丢弃左半部分（具有最小值）并检查右半部分。因此它不起作用

我认为它仅适用于数组具有 A[1] ≥ A[2] 和 A[n - 1] ≤ A[n] 的特殊属性的特殊情况。

于 2013-09-28T21:02:01.670 回答
0

原来的问题不完整。

刚刚在Find local minima in a array 中找到了完整的问题和详细的解释 ！- 不是我的博客

给定一个唯一整数数组，其前两个数字正在减少，最后两个数字正在增加，请在数组中找到一个局部最小值。如果数组中的数字小于其左右数字，则称为局部最小值。

例如，在数组 9,7,2,8,5,6,3,4 中，2 是一个局部最小值，因为它小于其左右数字 7 和 8。类似地，5 是另一个局部最小值，因为它在 8 之间和 6，都大于 5。

您需要找到任何一个局部最小值。

于 2014-07-11T17:08:59.390 回答
0

这是一个适用于 O(log n) 的解决方案。基本上，这适用于合并排序方法（分而治之）。

public class LocalMaxima {
    int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59};

    @Test 
    public  void localMaxima () {
        System.out.println((a[localMaxima(0,a.length-1)]));
    }

    int localMaxima(int low, int high) {
        if(high-low > 2) {
            int mid = (low+high)/2;
            return maxof(localMaxima(low,mid),localMaxima(mid+1, high));
        }
        else if(high-low == 1) {
            return maxof(high,low);
        }
        else if(high-low == 0) {
            return high;
        }
        if(high-low == 2) {
            return maxof(maxof(low, high),low+1);
        }
        return 0;
    }

    int maxof(int i, int j) {
        if(a[i] <a[j]) {
            return j;
        }
        else {
            return i;
        }
    }
}
于 2016-09-28T00:33:48.340 回答
0

实际上，我以前的算法可以修改为在 O(log n) 时间内获得所有最大值。我测试了它对提供的所有输入都很好。请让我知道您的反馈

public class LocalMaximas {

@Test
public void test () {
    System.out.println("maximas: please modify code to handle if array size is <= 2");

    int []a = {5,8,10,25,6,3,44,51,55,56,57,58,34,5,59,2};
    localMaximas(a);

    int []b = {9,7,2,8,5,6,3,4, 2}; //9,8,6,4
    localMaximas(b);

    int [] c= {15, 13, 12, 18, 19, 20, 7, 6, 5, 4, 3, 2, 1};//15,20
    localMaximas(c);
}

public  void localMaximas (int [] a) {
    System.out.println("\n\n");
    if(isMaxima(a,0)) {
        System.out.println(a[0]);
    }
    if(isMaxima(a,a.length-1)) {
        System.out.println(a[a.length-1]);
    }
    localMaximas(a,0,a.length-1);
}

int localMaximas(int []a,int low, int high) {
    int mid = (low+high)/2;
    if(high-low > 3) {     // more than 4 items in currently  divided array
        if(isMaxima(a,mid)) {
            System.out.println(a[mid]);
        }   
        localMaximas(a,low, mid);
        localMaximas(a,mid, high);
    }
    else if(high-low == 3){ //exactly 4 items in currently  divided array
        localMaximas(a,low, mid+1);
        localMaximas(a,mid, high);
    }   
    else if((high-low == 2) && (isMaxima(a,low+1))) {
        System.out.println(a[low+1]);
    }
    return 0;
}

int maxof(int []a, int i, int j) {
    if(a[i] <a[j]) {
        return j;
    }
    else {
        return i;
    }
}

boolean isMaxima(int []a ,int mid) {
    if(mid == 0) {
        if(maxof(a, mid, mid+1) == mid) {
            return true;
        }
        else {
            return false;
        }
    }
    else if(mid==a.length-1) {
        if(maxof(a,mid,mid-1) == mid) {
            return true;
        }
        else {
            return false;
        }
    }
    else {
        if((maxof(a, mid, mid+1) == mid) && (maxof(a, mid, mid-1) == mid)) {
            return true;
        }
        else {
            return false;
        }           
    }
}
}
于 2016-09-28T05:21:12.327 回答