Dado Q consultas de tres tipos donde cada consulta consta de un número.
- Agregar número de elemento a la izquierda
- Agregar número de elemento a la derecha
- Imprime el número de elementos a la derecha y a la izquierda del número de elemento dado .
La tarea es escribir un programa que realice las consultas anteriores.
Nota: Los elementos de las consultas 1 y 2 son distintos y 0 <= num <= 10 5 .
Ejemplos:
Entrada:
Q = 5
Consulta de tipo 1: num = 3
Consulta de tipo 2: num = 5
Consulta de tipo 1: num = 2
Consulta de tipo 1: num = 4
Consulta de tipo 3: num = 3
Salida: elemento en el derecha: 1 elemento a la izquierda: 2
Después de la consulta 1, el posicionamiento del elemento es 3
Después de la consulta 2, el posicionamiento del elemento es 35
Después de la consulta 3, el posicionamiento del elemento es 235
Después de la consulta 4, el posicionamiento del elemento es 4235
Así que hay 1 elemento a la derecha y 2 elementos a la izquierda de 3 cuando
se llama a la consulta 3.
Se pueden seguir los siguientes pasos para resolver el problema anterior.
- Inicialice una variable izquierda y derecha como 0, y dos arrays hash position[] y mark[] . position[] se usa para almacenar el índice de num a la izquierda y a la derecha y mark[] se usa para marcar si el num está a la izquierda o a la derecha.
- Para la consulta 1, aumente el recuento de la izquierda y marque la posición [num] como izquierda y marque [num] como 1.
- Para la consulta 2, aumente el recuento de la derecha y marque la posición [num] como derecha y marque [num] como 2
- Para la consulta-3, verifique si el número dado está presente a la derecha o a la izquierda usando la marca [].
- Si el número está presente a la derecha, entonces el número de elementos a la izquierda de num será (posición-izquierda[num]) , y el número de elementos a la derecha de num será (posición[num] – 1 + derecha ) .
- Si el número está presente a la izquierda, entonces el número de elementos a la derecha de num será (right-position[num]) , y el número de elementos a la izquierda de num será (position[num] – 1 + * izquierda) .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to print the number of elements
// on right and left of a given element
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
// function to perform query 1
void performQueryOne(int num, int* left, int* right,
int* position, int* mark)
{
// count number of elements on left
*left = *left + 1;
// store the index number
position[num] = *(left);
// mark the element is on left
mark[num] = 1;
}
// function to perform query 2
void performQueryTwo(int num, int* left, int* right,
int* position, int* mark)
{
// count number of elements on right
*right = *right + 1;
// store the index number
position[num] = *(right);
// mark the element is on right
mark[num] = 2;
}
// function to perform query 3
void performQueryThree(int num, int* left, int* right,
int* position, int* mark)
{
int toright, toleft;
// if the element is on right
if (mark[num] == 2) {
toright = *right - position[num];
toleft = position[num] - 1 + *left;
}
// if the element is on left
else if (mark[num] == 1) {
toleft = *left - position[num];
toright = position[num] - 1 + *right;
}
// not present
else {
cout << "The number is not there\n";
return;
}
cout << "The number of elements to right of "
<< num << ": " << toright;
cout << "\nThe number of elements to left of "
<< num << ": " << toleft;
}
// Driver Code
int main()
{
int left = 0, right = 0;
// hashing arrays
int position[MAXN] = { 0 };
int mark[MAXN] = { 0 };
int num = 3;
// query type-1
performQueryOne(num, &left, &right, position, mark);
// query type-2
num = 5;
performQueryTwo(num, &left, &right, position, mark);
// query type-2
num = 2;
performQueryOne(num, &left, &right, position, mark);
// query type-2
num = 4;
performQueryOne(num, &left, &right, position, mark);
// query type-3
num = 3;
performQueryThree(num, &left, &right, position, mark);
return 0;
}
Javascript
<script>
// JavaScript program to print the number of elements
// on right and left of a given element
const MAXN = 100005;
let left = 0, right = 0;
// hashing arrays
let position = new Array(MAXN).fill(0);
let mark = new Array(MAXN).fill(0);
// function to perform query 1
const performQueryOne = (num) => {
// count number of elements on left
left = left + 1;
// store the index number
position[num] = left;
// mark the element is on left
mark[num] = 1;
}
// function to perform query 2
const performQueryTwo = (num) => {
// count number of elements on right
right = right + 1;
// store the index number
position[num] = right;
// mark the element is on right
mark[num] = 2;
}
// function to perform query 3
const performQueryThree = (num) => {
let toright, toleft;
// if the element is on right
if (mark[num] == 2) {
toright = right - position[num];
toleft = position[num] - 1 + left;
}
// if the element is on left
else if (mark[num] == 1) {
toleft = left - position[num];
toright = position[num] - 1 + right;
}
// not present
else {
document.write("The number is not there<br/>");
return;
}
document.write(`The number of elements to right of ${num}: ${toright}`);
document.write(`<br/>The number of elements to left of ${num}: ${toleft}`);
}
// Driver Code
let num = 3;
// query type-1
performQueryOne(num);
// query type-2
num = 5;
performQueryTwo(num);
// query type-2
num = 2;
performQueryOne(num);
// query type-2
num = 4;
performQueryOne(num);
// query type-3
num = 3;
performQueryThree(num);
// This code is contributed by rakeshsahni
</script>
The number of elements to right of 3: 1 The number of elements to left of 3: 2
Complejidad de Tiempo: O(1) para cada consulta.
Espacio Auxiliar: O(MAXN), donde MAXN es 10 5 .