Dada una array arr[] de enteros de tamaño N , la tarea es contar el número de elementos cuyo valor es mayor que todos los K elementos a su derecha inmediata . Si hay menos de K números a la derecha del i-ésimo elemento, entonces el valor de todos ellos debe ser menor que el de la i-ésima persona.
Ejemplos:
Entrada: arr[] = {4, 3, 1, 2, 5}, N = 5, K = 1
Salida: 3
Explicación: El 1, 2 y 5 son los elementos cuyos valores son mayores que el elemento a su derecha ( Como k = 1 considere solo el siguiente). Mientras que el tercer elemento no se puede considerar debido al cuarto elemento cuyo valor es mayor que el valor del tercer elemento.Entrada: arr[] = {9, 7, 7, 7, 4}, N = 5, K = 3
Salida: 3
Explicación: Los elementos 1, 4 y 5 serán los elementos cuyos valores sean mayores que los 3 elementos después de.
Enfoque ingenuo: para cada elemento, marque los elementos K a su derecha inmediata y vea si es mayor que todos esos o no.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver siguiendo los siguientes pasos:
- Considere una cola para almacenar K elementos.
- Agregue K elementos desde el último a la cola y mantenga el máximo de los últimos K valores en una variable (digamos, max_value).
- Iterar sobre la array restante en dirección hacia atrás desde la posición (N – K).
- Mientras itera, extraiga un elemento de la cola y empuje el elemento actual en la cola.
- Si el elemento actual tiene un valor mayor que max_value, incremente el conteo y actualice max_value al elemento actual.
- De lo contrario, si el valor emergente es el mismo que max_value, busque el nuevo máximo de la cola.
- Devuelve el valor de conteo como el conteo del elemento cuyo valor es mayor que todos los k elementos a su derecha inmediata.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// maximum element in queue
int find_max(queue<int> q)
{
int ans = INT_MIN;
// Loop to find maximum from queue
while (!q.empty()) {
ans = max(ans, q.front());
q.pop();
}
return ans;
}
// Function to count the elements
// whose values are greater than
// all the k elements to its immediate right
int solve(int n, int k, vector<int> arr)
{
int max_value = INT_MIN;
queue<int> q;
int count = 0;
int p = n - k;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Traversing last k elements
for (int i = n - 1; i >= p; i--) {
q.push(arr[i]);
if (arr[i] > max_value) {
max_value = arr[i];
count++;
}
}
// Traversing rest of the elements
for (int i = p - 1; i >= 0; i--) {
int x = q.front();
q.pop();
q.push(arr[i]);
if (arr[i] > max_value) {
count++;
max_value = arr[i];
}
else {
if (x == max_value) {
// If popped value
// is same as max value
// then update max value
max_value = find_max(q);
}
}
}
return count;
}
// Driver Code Starts.
int main()
{
int N, K;
N = 5;
K = 1;
vector<int> arr = { 4, 3, 1, 2, 5};
cout << solve(N, K, arr) << "\n";
return 0;
}
Java
// Java code to implement the above approach
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class GFG {
// Function to find
// maximum element in queue
public static int find_max(Queue<Integer> q) {
int ans = Integer.MIN_VALUE;
// Loop to find maximum from queue
while (!q.isEmpty()) {
ans = Math.max(ans, q.peek());
q.remove();
}
return ans;
}
// Function to count the elements
// whose values are greater than
// all the k elements to its immediate right
public static int solve(int n, int k, ArrayList<Integer> arr) {
int max_value = Integer.MIN_VALUE;
Queue<Integer> q = new LinkedList<Integer>();
int count = 0;
int p = n - k;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Traversing last k elements
for (int i = n - 1; i >= p; i--) {
q.add(arr.get(i));
if (arr.get(i) > max_value) {
max_value = arr.get(i);
count++;
}
}
// Traversing rest of the elements
for (int i = p - 1; i >= 0; i--) {
int x = 0;
if (q.size() > 0) {
x = q.peek();
q.remove();
}
q.add(arr.get(i));
if (arr.get(i) > max_value) {
count++;
max_value = arr.get(i);
} else {
if (x == max_value) {
// If popped value
// is same as max value
// then update max value
max_value = find_max(q);
}
}
}
return count;
}
// Driver Code Starts.
public static void main(String args[]) {
int N, K;
N = 5;
K = 1;
ArrayList<Integer> arr = new ArrayList<>();
arr.add(4);
arr.add(3);
arr.add(1);
arr.add(2);
arr.add(5);
System.out.println(solve(N, K, arr));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python3 code to implement the above approach from queue import Queue import copy INT_MIN = -2147483648 # Function to find # maximum element in queue def find_max(q): ans = INT_MIN # Loop to find maximum from queue while (not q.empty()): ans = max(ans, q.get()) return ans # Function to count the elements # whose values are greater than # all the k elements to its immediate right def solve(n, k, arr): max_value = INT_MIN q = Queue() count = 0 p = n - k # Checking base cases if (n == 0): return 0 elif (k == 0): return n # Traversing last k elements for i in range(n - 1, p - 1, -1): q.put(arr[i]) if (arr[i] > max_value): max_value = arr[i] count += 1 # Traversing rest of the elements for i in range(p - 1, -1, -1): x = q.get() q.put(arr[i]) if (arr[i] > max_value): count += 1 max_value = arr[i] else: if (x == max_value): # If popped value is same # as max value then update # max value temp = Queue() for i in q.queue: temp.put(i) max_value = find_max(temp) return count # Driver code if __name__ == "__main__": N = 5 K = 1 arr = [ 4, 3, 1, 2, 5 ] print(solve(N, K, arr)) # This code is contributed by rakeshsahni
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find
// maximum element in queue
public static int find_max(Queue<int> q) {
int ans = int.MinValue;
// Loop to find maximum from queue
while (q.Count != 0) {
ans = Math.Max(ans, q.Peek());
q.Dequeue();
}
return ans;
}
// Function to count the elements
// whose values are greater than
// all the k elements to its immediate right
public static int solve(int n, int k, List<int> arr) {
int max_value = int.MinValue;
Queue<int> q = new Queue<int>();
int count = 0;
int p = n - k;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Traversing last k elements
for (int i = n - 1; i >= p; i--) {
q.Enqueue(arr[i]);
if (arr[i] > max_value) {
max_value = arr[i];
count++;
}
}
// Traversing rest of the elements
for (int i = p - 1; i >= 0; i--) {
int x = 0;
if (q.Count > 0) {
x = q.Peek();
q.Dequeue();
}
q.Enqueue(arr[i]);
if (arr[i] > max_value) {
count++;
max_value = arr[i];
} else {
if (x == max_value) {
// If popped value
// is same as max value
// then update max value
max_value = find_max(q);
}
}
}
return count;
}
// Driver Code Starts.
public static void Main(String []args) {
int N, K;
N = 5;
K = 1;
List<int> arr = new List<int>();
arr.Add(4);
arr.Add(3);
arr.Add(1);
arr.Add(2);
arr.Add(5);
Console.WriteLine(solve(N, K, arr));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript code to implement the above approach
// Function to find
// maximum element in queue
function find_max(q) {
let ans = Number.MIN_SAFE_INTEGER;
// Loop to find maximum from queue
while (q.length) {
ans = Math.max(ans, q[0]);
q.pop();
}
return ans;
}
// Function to count the elements
// whose values are greater than
// all the k elements to its immediate right
function solve(n, k, arr) {
let max_value = Number.MIN_SAFE_INTEGER;
let q = [];
let count = 0;
let p = n - k;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Traversing last k elements
for (let i = n - 1; i >= p; i--) {
q.push(arr[i]);
if (arr[i] > max_value) {
max_value = arr[i];
count++;
}
}
// Traversing rest of the elements
for (let i = p - 1; i >= 0; i--) {
let x = q[0];
q.pop();
q.push(arr[i]);
if (arr[i] > max_value) {
count++;
max_value = arr[i];
}
else {
if (x == max_value) {
// If popped value
// is same as max value
// then update max value
max_value = find_max(q);
}
}
}
return count;
}
// Driver Code Starts.
let N, K;
N = 5;
K = 1;
let arr = [4, 3, 1, 2, 5];
document.write(solve(N, K, arr))
// This code is contributed by gfgking.
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(K)
Enfoque de espacio optimizado: el problema se puede resolver con menos espacio utilizando el enfoque de dos punteros . Siga los pasos que se mencionan a continuación.
- Inicialice dos punteros (digamos «izquierda» y «derecha») apuntando al final de la array.
- El puntero izquierdo apunta al índice inicial de la ventana de tamaño K y el puntero derecho apunta al valor máximo en esa ventana.
- Si el valor en el puntero de la izquierda es mayor que el valor en el puntero de la derecha, aumente el número de respuestas en 1. (Porque significa que es mayor que todos los elementos K a su derecha inmediata)
- Si en algún momento el tamaño de la ventana excede K, disminuya el puntero derecho en uno y ajústelo para que apunte al valor máximo de la ventana actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the elements
// whose values are greater than
// all k elements to its immediate right
int solve(int n, int k, vector<int> arr)
{
int count = 1;
int left = n - 2, right = n - 1;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Loop to implement two-pointer approach
for (; left >= 0; left--) {
if (right - left > k) {
right--;
while (arr[left] > arr[right])
right--;
if (right == left)
count++;
}
else if (arr[left] > arr[right]) {
count++;
right = left;
}
}
return count;
}
// Driver Code Starts.
int main()
{
int N, K;
N = 5;
K = 1;
vector<int> arr = { 4, 3, 1, 2, 5};
cout << solve(N, K, arr);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
class GFG{
// Function to count the elements
// whose values are greater than
// all k elements to its immediate right
static int solve(int n, int k, int[] arr)
{
int count = 1;
int left = n - 2, right = n - 1;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Loop to implement two-pointer approach
for(; left >= 0; left--)
{
if (right - left > k)
{
right--;
while (arr[left] > arr[right])
right--;
if (right == left)
count++;
}
else if (arr[left] > arr[right])
{
count++;
right = left;
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int N, K;
N = 5;
K = 1;
int[] arr = { 4, 3, 1, 2, 5 };
System.out.println(solve(N, K, arr));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python 3 code to implement the above approach # Function to count the elements # whose values are greater than # all k elements to its immediate right def solve(n, k, arr): count = 1 left = n - 2 right = n - 1 # Checking base cases if (n == 0): return 0 elif (k == 0): return n # Loop to implement two-pointer approach while left >= 0: if (right - left > k): right -= 1 while (arr[left] > arr[right]): right -= 1 if (right == left): count += 1 elif (arr[left] > arr[right]): count += 1 right = left left -= 1 return count # Driver Code if __name__ == "__main__": N = 5 K = 1 arr = [4, 3, 1, 2, 5] print(solve(N, K, arr)) # This code is contributed by ukasp.
C#
// C# code to implement the above approach
using System;
public class GFG
{
// Function to count the elements
// whose values are greater than
// all k elements to its immediate right
static int solve(int n, int k, int[] arr)
{
int count = 1;
int left = n - 2, right = n - 1;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Loop to implement two-pointer approach
for(; left >= 0; left--)
{
if (right - left > k)
{
right--;
while (arr[left] > arr[right])
right--;
if (right == left)
count++;
}
else if (arr[left] > arr[right])
{
count++;
right = left;
}
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
int N, K;
N = 5;
K = 1;
int[] arr = { 4, 3, 1, 2, 5 };
Console.WriteLine(solve(N, K, arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript code to implement the above approach
// Function to count the elements
// whose values are greater than
// all k elements to its immediate right
function solve(n , k, arr)
{
var count = 1;
var left = n - 2, right = n - 1;
// Checking base cases
if (n == 0)
return 0;
else if (k == 0)
return n;
// Loop to implement two-pointer approach
for(; left >= 0; left--)
{
if (right - left > k)
{
right--;
while (arr[left] > arr[right])
right--;
if (right == left)
count++;
}
else if (arr[left] > arr[right])
{
count++;
right = left;
}
}
return count;
}
// Driver Code
var N, K;
N = 5;
K = 1;
var arr = [ 4, 3, 1, 2, 5 ];
document.write(solve(N, K, arr));
// This code is contributed by 29AjayKumar
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshalkhond y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA