Trouver des minima locaux dans un tableau

Le nombre de minima locaux peuvent être n/2; vous ne pouvez pas les énumérer toutes dans O(log n) fuseau.

utilisez un algorithme diviser pour mieux régner. Soit m = n / 2, et examiner la valeur A[m] (que est, l'élément dans le milieu du tableau).

Cas 1: A[m-1] < A[m]. Puis la moitié gauche du tableau doit contenir un minimum local, alors recurse sur la moitié gauche. Nous pouvons le montrer par contradiction: supposons Qu'un[i] n'est pas un minimum local pour chaque 0 ≤ i < m. Alors un[m-1] n'est pas un minimum local, ce qui implique Qu'un[m-2] < a[m-1]. De même, A[m -3] < a[m -2]. En continuant de cette manière, nous obtenir un[0] < A[1]. Mais alors un[0] est un minimum local, contrairement à notre hypothèse initiale.

cas 2: A[m + 1] > A [m]. Ensuite, la moitié droite du tableau doit contenir un minimum local, alors revenez sur la moitié droite. C'est symétrique au cas 1.

cas 3: A[m - 1] > A[m] et A[M + 1] < A[m]. Alors un [m] est un minimum local, alors retournez-le. La récurrence du temps de fonctionnement est T(n) = T(n/2) + Θ(1), ce qui donne T(n) = Θ (log n).

la question originale n'est pas complète.

je viens de trouver la question complète et l'explication complète et détaillée à trouver les minima locaux dans un tableau! - pas mon blog

étant donné un tableau d'entiers uniques dont les deux premiers nombres diminuent et les deux derniers nombres augmentent, trouvez un nombre dans le tableau qui est des minima locaux. Un nombre dans le tableau s'appelle les minima locaux s'il est plus petit que ses nombres de gauche et de droite.

Pour exemple dans le tableau 9,7,2,8,5,6,3,4 2 est un minimum local car il est plus petit que son numéro gauche et droit 7 et 8. De même, 5 est un autre minimum local puisqu'il se situe entre 8 et 6, tous deux supérieurs à 5.

vous devez trouver l'un des minima locaux.

votre algorithme ne fonctionnera pas pour ce tableau

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

ici, le minimum local est de 12.. mais quand je coche l'élément du milieu, qui est 7, votre algorithme rejettera la moitié gauche (qui a les minima) et vérifiera la moitié droite. Par conséquent, il ne fonctionne pas

je pense qu'il ne fonctionne que pour le cas particulier où le tableau a une propriété particulière d'Un[1] ≥ A[2] et A[n - 1] ≤ A [n].

Voici une solution qui fonctionne sur O(log n). Fondamentalement, cela fonctionne sur l'approche de tri de fusion (diviser pour mieux régner).

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;
        }
    }
}

en fait, mon algorithme précédent peut être modifié pour obtenir toutes les maxima dans le temps O(log n). J'ai testé que cela fonctionne très bien pour toutes les entrées fournies. S'il vous plaît laissez-moi savoir vos commentaires

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;
        }           
    }
}
}