Dada una array de N enteros con duplicados permitidos. Todos los elementos se clasifican del 1 al N en orden ascendente si son distintos. Si hay, digamos, x elementos repetidos de un valor particular, a cada elemento se le debe asignar un rango igual a la media aritmética de x rangos consecutivos.
Ejemplos:
Input : 20 30 10 Output : 2.0 3.0 1.0 Input : 10 12 15 12 10 25 12 Output : 1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0 10 is the smallest and there are two 10s so take the average of two consecutive ranks 1 and 2 i.e. 1.5 . Next smallest element is 12. Since, two elements are already ranked, the next rank that can be given is 3. However, there are three 12's so the rank of 2 is (3+4+5) / 3 = 4. Next smallest element is 15. There is only one 15 so 15 gets a rank of 6 since 5 elements are ranked. Next element is 25 and it gets a rank of 7. Input : 1, 2, 5, 2, 1, 60, 3 Output : 1.5, 3.5, 6.0, 3.5, 1.5, 7.0, 5.0
Explicación para la primera entrada:
Método I (Simple).
Considere que no hay elementos repetidos. En tal caso, el rango de cada elemento es simplemente 1 + el número de elementos más pequeños en la array. Ahora, si la array contuviera elementos repetidos, modifique los rangos considerando también el número de elementos iguales. Si hay exactamente r elementos que son menores que e y s elementos que son iguales a e, entonces e obtiene el rango dado por
(r + r+1 + r+2 ... r+s-1)/s [Separating all r's and applying natural number sum formula] = (r*s + s*(s-1)/2)/s = r + 0.5*(s-1)
Algoritmo
function rankify(A)
N = length of A
R is the array for storing ranks
for i in 0..N-1
r = 1, s = 1
for j in 0..N-1
if j != i and A[j] < A[i]
r += 1
if j != i and A[j] = A[i]
s += 1
// Assign Rank to A[i]
R[i] = r + 0.5*(s-1)
return R
La implementación del método se da a continuación.
C++
// CPP Code to find rank of elements
#include <bits/stdc++.h>
using namespace std;
// Function to find rank
void rankify(int* A , int n) {
// Rank Vector
float R[n] = {0};
// Sweep through all elements in A for each
// element count the number of less than and
// equal elements separately in r and s.
for (int i = 0; i < n; i++) {
int r = 1, s = 1;
for (int j = 0; j < n; j++) {
if (j != i && A[j] < A[i])
r += 1;
if (j != i && A[j] == A[i])
s += 1;
}
// Use formula to obtain rank
R[i] = r + (float)(s - 1) / (float) 2;
}
for (int i = 0; i < n; i++)
cout << R[i] << ' ';
}
// Driver Code
int main() {
int A[] = {1, 2, 5, 2, 1, 25, 2};
int n = sizeof(A) / sizeof(A[0]);
for (int i = 0; i < n; i++)
cout << A[i] << ' ';
cout << '\n';
rankify(A, n);
return 0;
}
// This code is contributed by Gitanjali.
Java
// Java Code to find rank of elements
public class GfG {
// Function to print m Maximum elements
public static void rankify(int A[], int n)
{
// Rank Vector
float R[] = new float[n];
// Sweep through all elements in A
// for each element count the number
// of less than and equal elements
// separately in r and s
for (int i = 0; i < n; i++) {
int r = 1, s = 1;
for (int j = 0; j < n; j++)
{
if (j != i && A[j] < A[i])
r += 1;
if (j != i && A[j] == A[i])
s += 1;
}
// Use formula to obtain rank
R[i] = r + (float)(s - 1) / (float) 2;
}
for (int i = 0; i < n; i++)
System.out.print(R[i] + " ");
}
// Driver code
public static void main(String args[])
{
int A[] = {1, 2, 5, 2, 1, 25, 2};
int n = A.length;
for (int i = 0; i < n; i++)
System.out.print(A[i] + " ");
System.out.println();
rankify(A, n);
}
}
// This code is contributed by Swetank Modi
Python3
# Python Code to find # rank of elements def rankify(A): # Rank Vector R = [0 for x in range(len(A))] # Sweep through all elements # in A for each element count # the number of less than and # equal elements separately # in r and s. for i in range(len(A)): (r, s) = (1, 1) for j in range(len(A)): if j != i and A[j] < A[i]: r += 1 if j != i and A[j] == A[i]: s += 1 # Use formula to obtain rank R[i] = r + (s - 1) / 2 # Return Rank Vector return R if __name__ == "__main__": A = [1, 2, 5, 2, 1, 25, 2] print(A) print(rankify(A))
C#
// C# Code to find rank of elements
using System;
public class GfG {
// Function to print m Maximum
// elements
public static void rankify(int []A, int n)
{
// Rank Vector
float []R = new float[n];
// Sweep through all elements
// in A for each element count
// the number of less than and
// equal elements separately in
// r and s
for (int i = 0; i < n; i++) {
int r = 1, s = 1;
for (int j = 0; j < n; j++)
{
if (j != i && A[j] < A[i])
r += 1;
if (j != i && A[j] == A[i])
s += 1;
}
// Use formula to obtain rank
R[i] = r + (float)(s - 1) / (float) 2;
}
for (int i = 0; i < n; i++)
Console.Write(R[i] + " ");
}
// Driver code
public static void Main()
{
int []A = {1, 2, 5, 2, 1, 25, 2};
int n = A.Length;
for (int i = 0; i < n; i++)
Console.Write(A[i] + " ");
Console.WriteLine();
rankify(A, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP Code to find rank of elements
// Function to find rank
function rankify($A , $n)
{
// Rank Vector
$R = array(0);
// Sweep through all elements in A for each
// element count the number of less than and
// equal elements separately in r and s.
for ($i = 0; $i < $n; $i++)
{
$r = 1;
$s = 1;
for ($j = 0; $j < $n; $j++)
{
if ($j != $i && $A[$j] < $A[$i])
$r += 1;
if ($j != $i && $A[$j] == $A[$i])
$s += 1;
}
// Use formula to obtain rank
$R[$i] = $r + (float)($s - 1) / (float) 2;
}
for ($i = 0; $i < $n; $i++)
print number_format($R[$i], 1) . ' ';
}
// Driver Code
$A = array(1, 2, 5, 2, 1, 25, 2);
$n = count($A);
for ($i = 0; $i < $n; $i++)
echo $A[$i] . ' ';
echo "\n";
rankify($A, $n);
// This code is contributed by Rajput-Ji
?>
Javascript
<script>
// JavaScript Code to find rank of elements
// Function to find rank
function rankify(A, n) {
// Rank Vector
var R = [...Array(n)];
// Sweep through all elements in A for each
// element count the number of less than and
// equal elements separately in r and s.
for (var i = 0; i < n; i++) {
var r = 1,
s = 1;
for (var j = 0; j < n; j++) {
if (j != i && A[j] < A[i]) r += 1;
if (j != i && A[j] == A[i]) s += 1;
}
// Use formula to obtain rank
R[i] = parseFloat(r + parseFloat(s - 1) / parseFloat(2));
}
for (var i = 0; i < n; i++)
document.write(parseFloat(R[i]).toFixed(1) + " ");
}
// Driver Code
var A = [1, 2, 5, 2, 1, 25, 2];
var n = A.length;
for (var i = 0; i < n; i++) document.write(A[i] + " ");
document.write("<br>");
rankify(A, n);
</script>
Producción:
[1, 2, 5, 2, 1, 25, 2] [1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0]
La Complejidad de Tiempo es O(N*N), mientras que la complejidad de espacio es O(1) (excluyendo el espacio requerido para mantener rangos)
Método II (Eficiente)
En este método, cree otra array (T) de tuplas. El primer elemento de la tupla almacena el valor mientras que el segundo elemento se refiere al índice del valor en la array. Luego, ordene T en orden ascendente usando el primer valor de cada tupla. Una vez ordenados, se garantiza que los elementos iguales se vuelvan adyacentes. Luego, simplemente camine hacia abajo en T, encuentre el número de elementos adyacentes y establezca rangos para cada uno de estos elementos. Utilice el segundo miembro de cada tupla para determinar los índices de los valores.
Algoritmo
function rankify_improved(A)
N = Length of A
T = Array of tuples (i,j),
where i = A[i] and j = i
R = Array for storing ranks
Sort T in ascending order
according to i
for j in 0...N-1
k = j
// Find adjacent elements
while A[k] == A[k+1]
k += 1
// No of adjacent elements
n = k - j + 1
// Modify rank for each
// adjacent element
for j in 0..n-1
// Get the index of the
// jth adjacent element
index = T[i+j][1]
R[index] = r + (n-1)*0.5
// Skip n ranks
r += n
// Skip n indices
j += n
return R
La implementación del código del método se proporciona a continuación.
C++
// CPP Code to find rank of elements
#include <bits/stdc++.h>
using namespace std;
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b)
{
return (a.first < b.first);
}
// Function to find rank
void rankify_improved(int A[] , int n) {
// Rank Vector
float R[n] = {0};
// Create an auxiliary array of tuples
// Each tuple stores the data as well
// as its index in A
vector <pair<int,int>> T(n);
for(int i = 0; i < n; i++)
{
T[i].first=A[i];
T[i].second=i;
}
// T[][0] is the data and T[][1] is
// the index of data in A
// Sort T according to first element
sort(T.begin(),T.end(),sortbysec);
float rank = 1, m = 1,i = 0;
while(i < n){
float j = i;
// Get no of elements with equal rank
while(j < n - 1 && T[j].first == T[j + 1].first)
j += 1;
m = j - i + 1;
for(int k=0;k<m;k++){
// For each equal element use formula
// obtain index of T[i+j][0] in A
int idx = T[i+k].second;
R[idx] = (double)(rank + (m - 1) * 0.5);
}
// Increment rank and i
rank += m;
i += m;
}
for (int i = 0; i < n; i++)
cout << (double)R[i] << ' ';
}
// Driver Code
int main() {
int A[] = {1, 2, 5, 2, 1, 25, 2};
int n = sizeof(A) / sizeof(A[0]);
for (int i = 0; i < n; i++)
cout << A[i] << ' ';
cout << '\n';
rankify_improved(A, n);
return 0;
}
// This code is contributed by Aarti_Rathi
Java
// Java implementation to find rank of elements
import java.util.Arrays;
import java.util.Comparator;
class Pair
{
// each element having its first and second
int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
// Function to find rank
static void rankify_improved(int A[] , int n)
{
// Rank Vector
float R[] = new float[n];
for(int i=0;i<n;i++)
{
R[i]=0;
}
// Create an auxiliary array of tuples
// Each tuple stores the data as well
// as its index in A
Pair T[] = new Pair[n];
// for each element of input array create a
// structure element to store its index and
// factors count
for (int i=0; i<n; i++)
{
T[i] = new Pair(A[i],i);
}
// T[][0] is the data and T[][1] is
// the index of data in A
// Sort T according to first element
Arrays.sort(T,new Comparator<Pair>() {
@Override
// compare method for the elements
// of the structure
public int compare(Pair e1, Pair e2) {
// if two elements have the same number
// of factors then sort them in increasing
// order of their index in the input array
if (e1.first == e2.first)
return e1.second > e2.second ? -1 : 1;
// sort in decreasing order of number of factors
return e1.first < e2.first ? -1 : 1;
}
});
float rank = 1, m = 1;
int i = 0;
while(i < n){
int j = i;
// Get no of elements with equal rank
while(j < n - 1 && T[j].first == T[j + 1].first)
j += 1;
m = j - i + 1;
for(int k=0;k<m;k++){
// For each equal element use formula
// obtain index of T[i+j][0] in A
int idx = T[i+k].second;
R[idx] = (float)((float)rank + (float)(m - 1) * 0.5);
}
// Increment rank and i
rank += m;
i += m;
}
for (int k=0; k<n; k++)
System.out.print((double)R[k]+" ");
}
// Driver code
public static void main(String args[])
{
int A[] = {1, 2, 5, 2, 1, 25, 2};
int n = A.length;
for (int i = 0; i < n; i++)
System.out.print(A[i] + " ");
System.out.println();
rankify_improved(A, n);
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python code to find # rank of elements def rankify_improved(A): # create rank vector R = [0 for i in range(len(A))] # Create an auxiliary array of tuples # Each tuple stores the data as well # as its index in A T = [(A[i], i) for i in range(len(A))] # T[][0] is the data and T[][1] is # the index of data in A # Sort T according to first element T.sort(key=lambda x: x[0]) (rank, n, i) = (1, 1, 0) while i < len(A): j = i # Get no of elements with equal rank while j < len(A) - 1 and T[j][0] == T[j + 1][0]: j += 1 n = j - i + 1 for j in range(n): # For each equal element use formula # obtain index of T[i+j][0] in A idx = T[i+j][1] R[idx] = rank + (n - 1) * 0.5 # Increment rank and i rank += n i += n return R if __name__ == "__main__": A = [1, 2, 5, 2, 1, 25, 2] print(A) print(rankify_improved(A))
Javascript
<script>
// JavaScript code to find
// rank of elements
function rankify_improved(A)
{
// create rank vector
let R = new Array(A.length).fill(0)
// Create an auxiliary array of tuples
// Each tuple stores the data as well
// as its index in A
let T = new Array(A.length);
for(let i = 0; i < A.length; i++)
{
T[i] = [A[i], i]
}
// T[][0] is the data and T[][1] is
// the index of data in A
// Sort T according to first element
T.sort((a,b) => a[0]-b[0])
let rank = 1, n = 1,i = 0
while(i < A.length){
let j = i
// Get no of elements with equal rank
while(j < A.length - 1 && T[j][0] == T[j + 1][0])
j += 1
n = j - i + 1
for(let j=0;j<n;j++){
// For each equal element use formula
// obtain index of T[i+j][0] in A
let idx = T[i+j][1]
R[idx] = rank + (n - 1) * 0.5
}
// Increment rank and i
rank += n
i += n
}
return R
}
// Driver code
let A = [1, 2, 5, 2, 1, 25, 2]
document.write(A,"</br>")
document.write(rankify_improved(A),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
[1, 2, 5, 2, 1, 25, 2] [1.5, 4.0, 6.0, 4.0, 1.5, 7.0, 4.0]
La complejidad del tiempo depende del procedimiento de clasificación que normalmente es O (N Log N). El espacio auxiliar es O(N), ya que necesitamos almacenar tanto los índices como los valores.
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA