Insérer, Supprimer, max dans O (1)

Le commentaire de @ KennyTM souligne un détail manquant important-insérer où, et supprimer d'où. Donc, je vais supposer que vous voulez toujours insérer et supprimer seulement d'une extrémité comme une pile.

Insertion (push) et Delete (pop) sont O (1).

Pour obtenir Max dans O (1), utilisez une pile supplémentaire pour enregistrer le max actuel qui correspond à la pile principale.

La solution suivante utilise O (1) mémoire supplémentaire et O(1) temps pour max, push et pop opérations. Gardez une variable max qui gardera une trace de l'élément max Actuel à un moment donné. Utilisons le fait que lorsque max est mis à jour, tous les éléments de la pile doivent être inférieurs au nouvel élément max. Lorsqu'une opération push se produit et que le nouvel élément (newElement) est supérieur au max actuel, nous poussons le max + newElement dans la pile et mettons à jour max = newElement.

Quand nous faisons une opération pop et nous trouvons que l'élément sauté actuel est supérieur au maximum actuel alors nous savons que c'est l'endroit où nous avions mis à jour notre pile pour contenir max+elem. Donc, l'élément réel à renvoyer est max et max = poppedElem-max.

Pour par exemple. si nous poussons 1, 2, 3, 4, 5 la variable stack et max ressemblera ci-dessous:

MAIN       Value of MAX
+---+      +---+
| 9 |      max = | 5 |
| 7 |      max = | 4 |
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Maintenant, disons que nous pop un élément, nous allons essentiellement pop, élément max (depuis top > max ) et mettre à jour l'élément max à (haut-max)

MAIN       Value of MAX
+---+      +---+
| 7 |      max = | 4 | = (9-5)
| 5 |      max = | 3 |
| 3 |      max = | 2 |
| 1 |      max = | 1 |
+---+      +---+

Maintenant, disons que nous poussons les chiffres 5, 4, 3, 2, 1, la pile ressemblera à:

MAIN       Value of MAX
+---+      +---+
| 1 |      max = | 5 |
| 2 |      max = | 5 |
| 3 |      max = | 5 |
| 4 |      max = | 5 |
| 5 |      max = | 5 |
+---+      +---+

Lorsque nous pop, le haut de la pile est sauté depuis top

Voici un pseudo code pour chacune des opérations pour une meilleure compréhension.

Elem max;
void Push(Elem x){
    if x < max :
        push(x);
    else{
        push(x+max);
        max = x;
    }
}
Elem Pop(){
    Elem p = pop();
    if |p| < |max|:
        return p;
    else{
        max = p - max;
        return max;
    }
}
Elem Max(){
    return max;
}

Push et pop sont des opérations de pile normales. Espérons que cette aide.

Si vous n'utilisez que des comparaisons, vous aurez du mal à trouver une telle structure de données.

Par exemple, vous pouvez insérer n éléments, obtenir max, supprimer max, etc. et trier les nombres dans le temps O (n), tandis que la limite inférieure théorique est Omega (nlogn).

Bien que la réponse de @Can Berk Güder soit correcte. Mais si nous avons une contrainte d'espace, nous pouvons faire beaucoup mieux même si les éléments ne sont pas distincts. Pour plus de détails, veuillez voir ma réponse Ici dans Java.

Le programme ci-dessous garde la trace des éléments max dans la pile de telle sorte que n'importe quel point de temps le pointeur supérieur nous donnerait le maximum dans la pile : Donc, max serait O (1), et nous pouvons trouver max par max[n]

ITEM   MAX

+---+  +---+
| 1 |  | 1 |
| 10|  | 10|
| 9 |  | 10|
| 19|  | 19| <--top
+---+  +---+

Programme Java:

public class StackWithMax {

private int[] item;
private int N = 0;
private int[] max;

public StackWithMax(int capacity){
    item = new int[capacity];//generic array creation not allowed
    max = new int[capacity];
}

public void push(int item){
    this.item[N++] = item;
    if(max[N-1] > item) {
        max[N] = max[N-1];
    } else {
        max[N] = item;
    }
}

public void pop() {
    this.item[N] = 0;
    this.max[N] = 0;
    N--;
}

public int findMax(){
    return this.max[N];
}
public static void main(String[] args) {
    StackWithMax max = new StackWithMax(10);
    max.push(1);
    max.push(10);
    max.push(9);
    max.push(19);
    System.out.println(max.findMax());
    max.pop();
    System.out.println(max.findMax());


}

}

Comme certains l'ont déjà souligné, la question manque d'informations. Vous ne spécifiez pas étaient à insérer / supprimer, ni la nature des données que nous traitons.

Quelques idées qui pourraient être utiles: Vous dites,

Insérer / Supprimer / opération maximale dans O (1)

Notez que si nous pouvons insérer, supprimer et trouver maximun dans O (1), alors nous pouvons utiliser cette technique hipotetical pour trier dans O (n), car nous pouvons insérer les N éléments, puis prendre max / delete et nous obtenons tous triés. Il est prouvé qu'aucun algorithme de tri basé sur des comparaisons ne peut trier en moins de O (nlogn), donc nous savons qu'aucun aproach basé sur une comparaison ne fonctionnera. En fait, l'une des façons les plus rapides connues de le faire est la file D'attente Brodal, mais son temps de suppression dépasse O (1).

Peut-être que la solution est quelque chose comme un arbre de base, si la complexité de toutes ces opérations est liée à la longueur de la clé comme oposée à la quantité de clés. Ceci n'est valide que s'ils vous permettent de lier la longueur de la clé par un autre nombre, de sorte que vous pouvez le considérer comme constante.

Mais peut-être que ce n'était pas quelque chose de générique. Une autre interprétation, est que l'insertion / suppression sont celles d'une pile classique. Dans ce cas restreint, vous pouvez utiliser le solutiom double pile que peut Berk güder vous a donné.

Une table de hachage peut prendre en charge insert / delete dans O (1), aucune idée de maximum cependant. Vous auriez probablement besoin de garder une trace de vous-même en quelque sorte.