Finding La mediana de una matriz no seleccionados en el tiempo lineal usando la función de biblioteca C ++ estándar

En este artículo, hablaremos de cómo encontrar la mediana de una matriz no clasificados y sin clasificar en la complejidad de tiempo lineal con la ayuda de nth_element función de la biblioteca estándar ()?

Requisito: std :: nth_element () en C ++

Planteamiento del problema:

Encuentra la mediana de una matriz sin clasificar.

¿Cuál es la mediana?

A mediana es una medida estadística que divide un conjunto ordenado de datos en dos mitades. La mediana es el punto de partición class cualquier lista ordenada. En el class de una matriz de mediana ordenada es el elemento medio. Si el tamaño de la matriz es impar entonces la mediana es simplemente el elemento medio y si el tamaño de la matriz es impar entonces la mediana es el promedio de los dos elementos intermedios.

Ejemplo:

matriz con forma rara:

array= [5, 4, 3, 1, 2]
If the array was sorted then it would be [1,2,3,4,5]
and the middle element would be 3
Thus the median is 3

matriz con tamaño aún:

array= [5, 4, 3, 1, 2, 6]
If the array was sorted then it would be [1, 2, 3, 4, 5, 6]
and the middle element would be 3 & 4
Thus the median is (3+4)/2 = 3.5

Por lo tanto, para encontrar la mediana de la matriz sin clasificar tenemos que encontrar el medio elemento (s) cuando se ordenará la matriz. No requerimos para ordenar todo el conjunto, más bien sólo necesita el elemento medio (s) si la matriz se solucionó.

Para ello podemos utilizar la función nth_element () de la biblioteca estándar que da la nth_element () si la matriz se solucionó.

Así que el algoritmo sería:

Si el tamaño del arreglo es impar:

Necesitamos solamente el elemento central que es sorted_array [n / 2] donde n es el número de elementos, y sorted_array es la versión clasificada de la matriz. Pero no necesitamos al deporte la matriz y no vamos a utilizar, como a continuación,

nth_element(array.begin(),array.begin()+n/2,array.end())
Where, array.begin()=start iterator to the array
array.end()=End iterator to the array
So the range is from start tio end the entire array
arr.begin()+n/2 = iterator to our desired nth element
After this array[n/2] will give us the middle element
if array was sorted which is median itself since size is odd.

Si el tamaño del arreglo es par:

Necesitamos elementos intermedios que son n / elemento día 2 y (n / 2- 1) -ésimo elemento.

Al igual que anteriormente, lo hicimos.

Para encontrar elemento n / 2 Tes

nth_element(array.begin(),array.begin()+n/2,array.end())
store array[n/2] to variable a
To find (n/2-1)th element
nth_element(array.begin(),array.begin()+(n-1)/2,array.end())
store array[n/2] to variable b
So, the median would be (a+b)/2.0
Remember don't leave doing integer division
as that will lead to wrong answer. That's why divide by 2.0 not 2

Ejemplo:

#include <bits/stdc++.h>
using namespace std;
//to print the vector
void print(vector<int> arr)
{
for (auto it : arr) {
cout << it << " ";
}
cout << endl;
}
int main()
{
int n;
cout << "Enter number of input elements n";
cin >> n;
//to see how it's initialized
cout << "Input the elementsn";
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Printing the array initially...n";
print(arr);
//array size odd
if (n % 2 == 1) {
//median is arr[n/2] if array is sorted
//can do the same using nth_element
nth_element(arr.begin(), arr.begin() + n / 2, arr.end());
cout << "Median is: " << arr[n / 2] << endl;
}
else { //array size even
//median is arr[n/2-1]+arr[n/2] if array is sorted
//n/2th element
nth_element(arr.begin(), arr.begin() + n / 2, arr.end());
int a = arr[n / 2];
//n/2-1 th element
nth_element(arr.begin(), arr.begin() + n / 2 - 1, arr.end());
int b = arr[n / 2 - 1];
cout << "Median is: " << (a + b) / 2.0 << endl;
}
return 0;
}

salida:

RUN 1:
Enter number of input elements
5
Input the elements
5 4 3 1 2
Printing the array initially...
5 4 3 1 2
Median is: 3
RUN 2:
Enter number of input elements
6
Input the elements
6 5 4 1 2 3
Printing the array initially...
6 5 4 1 2 3
Median is: 3.5


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *