Diseñe una estructura de datos que pueda realizar las siguientes operaciones
- agregar() en O (n)
- getMinimum() en O(1)
- deleteMinimum() en O(1)
Fuente: Entrevista de MakeMyTrip.
- Mantenga una lista enlazada con elementos en orden creciente.
- Mueve el cabezal a la siguiente posición en caso de eliminar la operación Min.
- Devuelve el primer elemento en caso de obtener la operación mínima.
// Java code for linked list to
// perform required operations
import java.util.*;
// Node class
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// main class
class MinDS
{
Node start;
public MinDS()
{
start = null;
}
// Function to add element
void addElement(int d)
{
Node tmp = new Node(d);
// If linked list is empty
if (start == null)
{
start = tmp;
return;
}
// If head itself is greater
if (d < start.data)
{
tmp.next = start;
start = tmp;
return;
}
// If need to insert somewhere in middle
Node prev = start;
Node ptr = start.next;
while (ptr != null)
{
if (d < ptr.data)
{
tmp.next = ptr;
prev.next = tmp;
return;
}
else
{
prev = ptr;
ptr = ptr.next;
}
}
prev.next = tmp;
}
// Function to get minimum
int getMin()
{
return start.data;
}
// Function to delete minimum
int delMin()
{
int min = start.data;
start = start.next;
return min;
}
// Function to print elements
void print()
{
Node ptr = start;
System.out.print("Elements: ");
while (ptr != null)
{
System.out.print(ptr.data + ", ");
ptr = ptr.next;
}
System.out.println("\n");
}
// Driver code
public static void main(String[] args)
{
MinDS x = new MinDS();
x.addElement(10);
x.addElement(20);
x.addElement(5);
x.addElement(15);
x.print();
System.out.println("Get Min: " + x.getMin());
System.out.println("Del Min: " + x.delMin());
x.print();
System.out.println("Min: " + x.getMin());
}
}
Producción:
Elements: 5, 10, 15, 20, Get Min: 5 Del Min: 5 Elements: 10, 15, 20, Min: 10
Publicación traducida automáticamente
Artículo escrito por amansharma26 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA