Dada una array arr[ ] de tamaño N , la tarea es encontrar el rango del elemento restante en una array después de realizar la operación dada:
- En cada operación, elija elementos de ambos extremos y elimínelos e inserte el máximo de esos valores en la posición del elemento izquierdo y muévase un paso hacia el centro desde ambos extremos y siga realizando esta operación.
- En el próximo ciclo siga realizando la misma operación pero en lugar de max, inserte min de los elementos esta vez.
- Realice esta operación en ciclos alternos hasta que solo quede un elemento en la array.
- El rango es la posición del elemento restante en la array original cuando se ordena en orden creciente. (Los elementos con los mismos valores se consideran solo para el orden ordenado)
Ejemplos:
Entrada: arr = { 4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89}
Salida: 6
Explicación: Ver el diagrama que se muestra a continuación
24 es el sexto elemento más pequeño. Los elementos con los mismos valores se consideran una vez.
Entrada: N = {20, 4, 5, 35, 6, 22, 4, 34}
Salida: 6
Enfoque: La solución se basa en el enfoque de dos punteros . Siga los pasos que se mencionan a continuación:
- Tome c como 1 , lo que indicará el número de iteraciones.
- Tome 2 punteros, comience como cero y termine como N-1 .
- Compare el elemento en el índice s y e .
- Si c es impar , tome el máximo del elemento ; de lo contrario, tome el mínimo del elemento y guárdelo en una array.
- Incremente s , disminuya e y repita hasta que s != e .
- Incrementar c en 1
- Repita el paso 2 hasta que la longitud de arr sea 1.
- Elimine el duplicado de arr[] y ordénelo, ahora encuentre el rango del elemento restante.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find rank of number in array
int rankOfNum(vector<int>& num)
{
// Copying array to S
vector<int> S = num;
// c count no of iterations
int c = 1;
while (S.size() != 1) {
// s is starting index
int s = 0;
// e is ending index
int e = S.size() - 1;
// Empty array to store
// result of comparisons.
vector<int> l;
// loop till s <= e
while (s <= e) {
// In odd iterations take
// maximum of element.
if (c % 2 == 1)
l.push_back(max(S[s], S[e]));
// In even Iterations
// take minimum of element.
else {
l.push_back(min(S[s], S[e]));
}
// Increment s by 1
// and decrement e by 1
s += 1;
e -= 1;
}
// Assigning l to S
S = l;
// Increment iteration value by 1
c += 1;
}
// Converting list into set and again to list
// so that all duplicate will get removed
set<int> setx;
for (auto dt : num)
setx.insert(dt);
// Finding index of remained element
int p = distance(setx.begin(), setx.find(S[0]));
// Returning the rank of element
return p + 1;
}
// Driver code
int main()
{
// Original array
vector<int> arr
= { 4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89 };
// Calling function
int s = rankOfNum(arr);
// Print its rank
cout << s;
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java code for the above approach
import java.util.*;
class GFG{
// Function to find rank of number in array
static int rankOfNum(Integer[] num)
{
// Copying array to S
List<Integer> S = Arrays.asList(num);
// c count no of iterations
int c = 1;
while (S.size() != 1) {
// s is starting index
int s = 0;
// e is ending index
int e = S.size() - 1;
// Empty array to store
// result of comparisons.
ArrayList<Integer> l = new ArrayList<Integer>();
// loop till s <= e
while (s <= e) {
// In odd iterations take
// maximum of element.
if (c % 2 == 1)
l.add(Math.max(S.get(s), S.get(e)));
// In even Iterations
// take minimum of element.
else {
l.add(Math.min(S.get(s), S.get(e)));
}
// Increment s by 1
// and decrement e by 1
s += 1;
e -= 1;
}
// Assigning l to S
S = l;
// Increment iteration value by 1
c += 1;
}
// Converting list into set and again to list
// so that all duplicate will get removed
HashSet<Integer> setx = new HashSet<Integer>();
for (int dt : num)
setx.add(dt);
// Finding index of remained element
List<Integer> l = new LinkedList<>(setx);
Collections.sort(l);
int p = l.indexOf(S.get(0));
// Returning the rank of element
return p + 1;
}
// Driver code
public static void main(String[] args)
{
// Original array
Integer[] arr
= { 4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89 };
// Calling function
int s = rankOfNum(arr);
// Print its rank
System.out.print(s);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code to implement above approach # Function to find rank of number in array def rankOfNum(num): # Copying array to S S = num[:] # c count no of iterations c = 1 while len(S) != 1: # s is starting index s = 0 # e is ending index e = len(S) - 1 # Empty array to store # result of comparisons. l = [] # loop till s <= e while s <= e: # In odd iterations take # maximum of element. if c % 2 == 1: l.append(max(S[s], S[e])) # In even Iterations # take minimum of element. else: l.append(min(S[s], S[e])) # Increment s by 1 # and decrement e by 1 s += 1 e -= 1 # Assigning l to S S = l # Increment iteration value by 1 c += 1 # Converting list into set and again to list # so that all duplicate will get removed setx = list(set(num)) # Sorting to get rank setx.sort() # Finding index of remained element p = setx.index(S[0]) # Returning the rank of element return p + 1 if __name__ == "__main__": # Original array arr = [4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89] # Calling function s = rankOfNum(arr) # Print its rank print(str(s))
C#
// C# code for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
class GFG {
// Function to find rank of number in array
static int rankOfNum(List<int> num)
{
// Copying array to S
List<int> S = num;
// c count no of iterations
int c = 1;
while (S.Count != 1) {
// s is starting index
int s = 0;
// e is ending index
int e = S.Count - 1;
// Empty array to store
// result of comparisons.
List<int> l = new List<int>();
// loop till s <= e
while (s <= e) {
// In odd iterations take
// maximum of element.
if (c % 2 == 1)
l.Add(Math.Max(S[s], S[e]));
// In even Iterations
// take minimum of element.
else {
l.Add(Math.Min(S[s], S[e]));
}
// Increment s by 1
// and decrement e by 1
s += 1;
e -= 1;
}
// Assigning l to S
S = l;
// Increment iteration value by 1
c += 1;
}
// Converting list into set and again to list
// so that all duplicate will get removed
HashSet<int> setx = new HashSet<int>();
foreach(var dt in num) setx.Add(dt);
// Finding index of remained element
List<int> setxList = setx.ToList();
setxList.Sort();
int p = setxList.IndexOf(S[0]);
// Returning the rank of element
return p + 1;
}
// Driver code
public static void Main()
{
// Original array
List<int> arr = new List<int>() {
4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89
};
// Calling function
int s = rankOfNum(arr);
// Print its rank
Console.Write(s);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to find rank of number in array
function rankOfNum(num) {
// Copying array to S
let S = [...num]
// c count no of iterations
c = 1
while (S.length != 1) {
// s is starting index
s = 0
// e is ending index
e = S.length - 1
// Empty array to store
// result of comparisons.
l = []
// loop till s <= e
while (s <= e) {
// In odd iterations take
// maximum of element.
if (c % 2 == 1)
l.push(Math.max(S[s], S[e]))
// In even Iterations
// take minimum of element.
else {
l.push(Math.min(S[s], S[e]))
}
// Increment s by 1
// and decrement e by 1
s += 1
e -= 1
}
// Assigning l to S
S = [...l]
// Increment iteration value by 1
c += 1
}
// Converting list into set and again to list
// so that all duplicate will get removed
let setx = new Set([...num])
// Sorting to get rank
t = [...setx].sort(function (a, b) { return a - b })
// Finding index of remained element
let p = t.indexOf(S[0])
// Returning the rank of element
return p + 1
}
// Original array
arr = [4, 5, 3, 56, 3, 24, 5, 6, 22, 4, 55, 50, 89]
// Calling function
s = rankOfNum(arr)
// Print its rank
document.write((s))
// This code is contributed by Potta Lokesh
</script>
Producción
6
Complejidad de tiempo: O(N)
Complejidad de espacio: O(N), ya que se ha tomado n espacio adicional
Publicación traducida automáticamente
Artículo escrito por harshdeepmahajan88 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA