Dada una array binaria arr[] , la tarea es diseñar una estructura de datos que admita las siguientes operaciones en O(1).
- Tipo 1: elimine e imprima el 0 más a la izquierda de la array.
- Tipo 2: elimine e imprima el 1 más a la izquierda de la array.
- Tipo 3: elimine e imprima el elemento más a la izquierda de la array.
Si alguno de los elementos solicitados no está en la array, imprima -1.
Ejemplos:
Entrada: arr[] = {1, 0, 1, 1, 1}, q[] = {1, 3, 1}
Salida:
0
1
-1 Consulta
tipo 1: Imprime 0 y la array se convierte en {1, 1, 1, 1}
Consulta de tipo 3: Imprimir 1, arr[] = {1, 1, 1}
Consulta de tipo 1: No quedan 0, así que imprime -1
Entrada: arr[] = {1, 0, 1, 0 , 1}, q[] = {3, 3, 3}
Salida:
1
0
1
Enfoque ingenuo: un enfoque simple es insertar todos los elementos en una cola que admita el primero en entrar, el primero en salir. Este enfoque funcionará en O(1) para encontrar el elemento más a la izquierda en la array, pero no puede encontrar el 1 más a la izquierda o el 0 más a la izquierda en O(1).
Enfoque eficiente: cree dos colas, la primera cola almacenará los índices de los 0 en el orden de aparición y la segunda cola almacenará los índices de los 1 en el orden de aparición. Ahora, las operaciones dadas se pueden realizar de la siguiente manera:
- Tipo 1: Imprima la eliminación de la cabeza de la primera cola en O(1).
- Tipo 2: Imprima y elimine el encabezado de la segunda cola en O(1).
- Tipo 3: compare el encabezado de ambas colas y devuelva el que tiene un índice mínimo y luego elimínelo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// To store the indices of 0s and 1s
static queue<int> zero;
static queue<int> one ;
// Function to return the leftmost 0
static int getLeftMostZero()
{
// If there are no 0s
if (zero.empty())
return -1;
// pop the head of the queue
zero.pop();
return 0;
}
// Function to return the leftmost 1
static int getLeftMostOne()
{
// If there are no 1s
if (one.empty())
return -1;
// pop the head of the queue
one.pop();
return 1;
}
// Function to return the pre-calculate array
// such that arr[i] stores the count of
// valid numbers in the range [0, i]
int getLeftMostElement()
{
// If there are no elements left
if (zero.empty() && one.empty())
return -1;
// If only 1s are there
else if (zero.empty())
{
one.pop();
return 1;
}
// If only 0s are there
else if (one.empty())
{
zero.pop();
return 0;
}
// Get the element which is at
// the left-most position
int res = (zero.front() < one.front()) ? 0 : 1;
if (res == 0)
zero.pop();
else
one.pop();
return res;
}
// Function to perform the queries
void performQueries(int arr[], int n,
int queries[], int q)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == 0)
zero.push(i);
else
one.push(i);
}
// For every query
for (int i = 0; i < q; i++)
{
// Get its type
int type = queries[i];
switch (type)
{
// Perform type 1 query
case 1:
cout << (getLeftMostZero())
<< endl;
break;
// Perform type 2 query
case 2:
cout << (getLeftMostOne())
<< endl;
break;
// Perform type 3 query
case 3:
cout << (getLeftMostElement())
<< endl;
break;
}
}
}
// Driver code
int main()
{
int arr[] = { 1, 0, 1, 1, 1 };
int n = sizeof(arr) / sizeof(int);
int queries[] = { 1, 3, 1 };
int q = sizeof(queries) / sizeof(int);
performQueries(arr, n, queries, q);
}
// This code is contributed by andrew1234
Java
// Java implementation of the approach
import java.util.*;
class GFG {
// Function to return the leftmost 0
static int getLeftMostZero(Queue<Integer> zero)
{
// If there are no 0s
if (zero.isEmpty())
return -1;
// Remove the head of the queue
zero.remove();
return 0;
}
// Function to return the leftmost 1
static int getLeftMostOne(Queue<Integer> one)
{
// If there are no 1s
if (one.isEmpty())
return -1;
// Remove the head of the queue
one.remove();
return 1;
}
// Function to return the pre-calculate array
// such that arr[i] stores the count of
// valid numbers in the range [0, i]
static int getLeftMostElement(Queue<Integer> zero, Queue<Integer> one)
{
// If there are no elements left
if (zero.isEmpty() && one.isEmpty())
return -1;
// If only 1s are there
else if (zero.isEmpty()) {
one.remove();
return 1;
}
// If only 0s are there
else if (one.isEmpty()) {
zero.remove();
return 0;
}
// Get the element which is at
// the left-most position
int res = (zero.peek() < one.peek()) ? 0 : 1;
if (res == 0)
zero.remove();
else
one.remove();
return res;
}
// Function to perform the queries
static void performQueries(int arr[], int n, int queries[], int q)
{
// To store the indices of 0s and 1s
Queue<Integer> zero = new LinkedList<>();
Queue<Integer> one = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (arr[i] == 0)
zero.add(i);
else
one.add(i);
}
// For every query
for (int i = 0; i < q; i++) {
// Get its type
int type = queries[i];
switch (type) {
// Perform type 1 query
case 1:
System.out.println(getLeftMostZero(zero));
break;
// Perform type 2 query
case 2:
System.out.println(getLeftMostOne(one));
break;
// Perform type 3 query
case 3:
System.out.println(getLeftMostElement(zero, one));
break;
}
}
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 0, 1, 1, 1 };
int n = arr.length;
int queries[] = { 1, 3, 1 };
int q = queries.length;
performQueries(arr, n, queries, q);
}
}
Python3
# Python3 implementation of the approach from collections import deque # To store the indices of 0s and 1s zero = deque() one = deque() # Function to return the leftmost 0 def getLeftMostZero(): # If there are no 0s if not len(zero): return -1 # pop the head of the queue zero.popleft() return 0 # Function to return the leftmost 1 def getLeftMostOne(): # If there are no 1s if not len(one): return -1 # pop the head of the queue one.popleft() return 1 # Function to return the pre-calculate array # such that arr[i] stores the count of # valid numbers in the range [0, i] def getLeftMostElement(): # If there are no elements left if not len(zero) and not len(one): return -1 # If only 1s are there elif not len(zero): one.popleft() return 1 # If only 0s are there elif not len(one): zero.popleft() return 0 # Get the element which is at # the left-most position res = 0 if zero[0] < one[0] else 1 if res == 0: zero.popleft() else: one.popleft() return res # Function to perform the queries def performQueries(arr: list, n: int, queries: list, q: int): for i in range(n): if arr[i] == 0: zero.append(i) else: one.append(i) # For every query for i in range(q): # Get its type type = queries[i] # Perform type 1 query if type == 1: print(getLeftMostZero()) # Perform type 2 query elif type == 2: print(getLeftMostOne()) # Perform type 3 query elif type == 3: print(getLeftMostElement()) # Driver Code if __name__ == "__main__": arr = [1, 0, 1, 1, 1] n = len(arr) queries = [1, 3, 1] q = len(queries) performQueries(arr, n, queries, q) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the leftmost 0
static int getLeftMostZero(Queue<int> zero)
{
// If there are no 0s
if (zero.Count == 0)
return -1;
// Remove the head of the queue
zero.Dequeue();
return 0;
}
// Function to return the leftmost 1
static int getLeftMostOne(Queue<int> one)
{
// If there are no 1s
if (one.Count == 0)
return -1;
// Remove the head of the queue
one.Dequeue();
return 1;
}
// Function to return the pre-calculate array
// such that arr[i] stores the count of
// valid numbers in the range [0, i]
static int getLeftMostElement(Queue<int> zero,
Queue<int> one)
{
// If there are no elements left
if (zero.Count == 0 && one.Count == 0)
return -1;
// If only 1s are there
else if (zero.Count == 0)
{
one.Dequeue();
return 1;
}
// If only 0s are there
else if (one.Count == 0)
{
zero.Dequeue();
return 0;
}
// Get the element which is at
// the left-most position
int res = (zero.Peek() < one.Peek()) ? 0 : 1;
if (res == 0)
zero.Dequeue();
else
one.Dequeue();
return res;
}
// Function to perform the queries
static void performQueries(int []arr, int n,
int []queries, int q)
{
// To store the indices of 0s and 1s
Queue<int> zero = new Queue<int>();
Queue<int> one = new Queue<int>();
for (int i = 0; i < n; i++)
{
if (arr[i] == 0)
zero.Enqueue(i);
else
one.Enqueue(i);
}
// For every query
for (int i = 0; i < q; i++)
{
// Get its type
int type = queries[i];
switch (type)
{
// Perform type 1 query
case 1:
Console.WriteLine(getLeftMostZero(zero));
break;
// Perform type 2 query
case 2:
Console.WriteLine(getLeftMostOne(one));
break;
// Perform type 3 query
case 3:
Console.WriteLine(getLeftMostElement(zero, one));
break;
}
}
}
// Driver code
public static void Main(String []args)
{
int []arr = { 1, 0, 1, 1, 1 };
int n = arr.Length;
int []queries = { 1, 3, 1 };
int q = queries.Length;
performQueries(arr, n, queries, q);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the leftmost 0
function getLeftMostZero(zero)
{
// If there are no 0s
if (zero.length==0)
return -1;
// Remove the head of the queue
zero.shift();
return 0;
}
// Function to return the leftmost 1
function getLeftMostOne(one)
{
// If there are no 1s
if (one.length==0)
return -1;
// Remove the head of the queue
one.shift();
return 1;
}
// Function to return the pre-calculate array
// such that arr[i] stores the count of
// valid numbers in the range [0, i]
function getLeftMostElement(zero,one)
{
// If there are no elements left
if (zero.length==0 && one.length==0)
return -1;
// If only 1s are there
else if (zero.length==0) {
one.shift();
return 1;
}
// If only 0s are there
else if (one.length==0) {
zero.shift();
return 0;
}
// Get the element which is at
// the left-most position
let res = (zero[0] < one[0]) ? 0 : 1;
if (res == 0)
zero.shift();
else
one.shift();
return res;
}
// Function to perform the queries
function performQueries(arr,n,queries,q)
{
// To store the indices of 0s and 1s
let zero = [];
let one = [];
for (let i = 0; i < n; i++) {
if (arr[i] == 0)
zero.push(i);
else
one.push(i);
}
// For every query
for (let i = 0; i < q; i++) {
// Get its type
let type = queries[i];
switch (type) {
// Perform type 1 query
case 1:
document.write(getLeftMostZero(zero)+"<br>");
break;
// Perform type 2 query
case 2:
document.write(getLeftMostOne(one)+"<br>");
break;
// Perform type 3 query
case 3:
document.write(getLeftMostElement(zero, one)+"<br>");
break;
}
}
}
// Driver code
let arr=[1, 0, 1, 1, 1];
let n = arr.length;
let queries=[1, 3, 1 ];
let q = queries.length;
performQueries(arr, n, queries, q);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
0 1 -1