首页 文章

在数组中查找局部最小值

提问于
浏览
27

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

我知道如果只有一个局部最小值,那么我们可以用修改后的二进制搜索来解决 . 但是如果知道阵列中存在多个局部最小值,那么可以在 O(log n) 时间内解决吗?

7 回答

  • 0

    原来的问题还没有完成 .

    刚刚在Find local minima in an array找到了完整的问题和详尽的解释! - 不是我的博客

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

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

    你需要找到任何一个本地最小值 .

  • 5

    您的算法不适用于此阵列

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

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

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

  • 0

    使用分而治之算法 . 设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) .

  • 0

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

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

    • 如果只有一个元素,则保证是局部最小值 .

    • 如果有多个元素,请查看中间元素 . 如果它完成了's a local minimum, you' . 否则,它旁边的至少一个元素必须小于它 . 现在,想象如果你从一个较小的元素开始并逐渐向远离中间元素的方向移动到阵列的一端,会发生什么 . 在每一步,要么下一个元素小于前一个元素,要么它会更大 . 最终,您将以这种方式命中数组的末尾,或者您将达到局部最小值 . 请注意,这意味着您 could 执行此操作以查找本地最小值 . 但是,我们使用这样一个事实,即在数组的这一半中存在局部最小值作为丢弃数组的一半的理由 . 在剩下的情况下,我们保证找到当地的最低要求 .

    因此,您可以构建以下递归算法:

    • 如果只有一个数组元素,则它是局部最小值 .

    • 如果有两个数组元素,请检查每个元素 . 一个必须是当地的最低要求 .

    • 否则,请查看数组的中间元素 . 如果是当地最低要求,请将其退回 . 否则,至少一个相邻值必须小于此值 . 递归包含较小元素(但不是中间)的数组的一半 .

    请注意,这具有重现关系

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

    使用主定理,您可以根据需要显示此算法在时间O(log n)中运行 .

    希望这可以帮助!

    另请注意,只有当数组边缘小于相邻元素时,此算法的边数才算作局部最小值,此算法才有效 .

  • 57

    局部最小值的数量可以是 n/2 ;你无法在 O(log n) 时间内全部枚举它们 .

  • 6

    这是一个适用于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;
            }
        }
    }
    
  • 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;
            }           
        }
    }
    }
    

相关问题