Comment trouver le kème élément le plus grand dans un tableau non trié de longueur n dans O (n)?
https://stackoverflow.com/questions/251781
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je pense qu’il existe un moyen de trouver le kème élément le plus grand dans un tableau non trié de longueur n dans O (n). Ou peut-être que c'est & "Attendu" & "; O (n) ou quelque chose. Comment pouvons-nous faire cela?
La solution
Cela s’appelle la recherche de la statistique d’ordre k-ème . Il existe un algorithme aléatoire très simple (appelé quickselect ) prenant O(n) le temps moyen, O(n^2) le pire des cas, et un algorithme assez compliqué non aléatoire (appelé introselect ) prendre <=> le pire des cas. Wikipedia , mais ce n'est pas très bon.
Tout ce dont vous avez besoin se trouve dans ces diapositives PowerPoint . Il suffit d'extraire l'algorithme de base de <=> l'algorithme du cas le plus défavorable (introselect):
Select(A,n,i):
Divide input into ⌈n/5⌉ groups of size 5.
/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)
/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)
Il est également très bien détaillé dans le livre Introduction to Algorithms de Cormen et al.
Autres conseils
Si vous voulez un véritable O(n) algorithme, par opposition à O(kn) ou quelque chose du genre, vous devez alors utiliser quickselect (il s'agit en fait de tri rapide qui consiste à jeter la partition qui ne vous intéresse pas). Mon prof a une excellente écriture, avec l'analyse d'exécution: ( référence )
L'algorithme QuickSelect trouve rapidement le k-ème plus petit élément d'un tableau non trié de n éléments. Il s'agit d'un RandomizedAlgorithm , nous calculons donc le cas le plus défavorable attendu temps d'exécution.
Voici l'algorithme.
QuickSelect(A, k)
let r be chosen uniformly at random in the range 1 to length(A)
let pivot = A[r]
let A1, A2 be new arrays
# split into a pile A1 of small elements and A2 of big elements
for i = 1 to n
if A[i] < pivot then
append A[i] to A1
else if A[i] > pivot then
append A[i] to A2
else
# do nothing
end for
if k <= length(A1):
# it's in the pile of small elements
return QuickSelect(A1, k)
else if k > length(A) - length(A2)
# it's in the pile of big elements
return QuickSelect(A2, k - (length(A) - length(A2))
else
# it's equal to the pivot
return pivot
Quelle est la durée d'exécution de cet algorithme? Si l’adversaire nous envoie des pièces, il se peut que le pivot soit toujours l’élément le plus grand et que k soit toujours égal à 1, ce qui donne un temps de parcours de
T(n) = Theta(n) + T(n-1) = Theta(n2)Mais si les choix sont effectivement aléatoires, le temps d'exécution attendu est donné par
T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1)) où nous faisons l'hypothèse pas tout à fait raisonnable que la récursion atterrit toujours dans le plus grand de A1 ou A2.
Supposons que T(n) <= an pour certains a. Ensuite, nous obtenons
T(n)
<= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
= cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
<= cn + 2 (1/n) ∑i=floor(n/2) to n ai et maintenant nous devons d’une manière ou d’une autre obtenir la somme épouvantable à droite du signe plus pour absorber le cn à gauche. Si nous le lions simplement comme 2(1/n) ∑i=n/2 to n an, nous obtenons approximativement 2(1/n)(n/2)an = an. Mais c'est trop gros - il n'y a pas de place pour un extra floor(n/2). Alors développons la somme en utilisant la formule de la série arithmétique:
∑i=floor(n/2) to n i
= ∑i=1 to n i - ∑i=1 to floor(n/2) i
= n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2
<= n2/2 - (n/4)2/2
= (15/32)n2 où nous tirons parti de n étant & "suffisamment grand &"; pour remplacer les n/4 facteurs laids par des facteurs beaucoup plus propres (et plus petits) a > 16c. Maintenant, nous pouvons continuer avec
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an a fourni T(n) = O(n).
Ceci donne Omega(n). C'est clairement T(n) = Theta(n), donc nous obtenons <=>.
Un rapide Google sur ce ("kème plus grand tableau d'éléments") a renvoyé ceci: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
"Make one pass through tracking the three largest values so far."
(c'était spécifiquement pour 3d le plus grand)
et cette réponse:
Build a heap/priority queue. O(n)
Pop top element. O(log n)
Pop top element. O(log n)
Pop top element. O(log n)
Total = O(n) + 3 O(log n) = O(n)
Vous aimez le tri rapide. Choisissez un élément au hasard et poussez tout plus haut ou plus bas. À ce stade, vous saurez quel élément vous avez réellement sélectionné et si c'est le kth élément que vous avez terminé, sinon, vous répétez avec la corbeille (supérieure ou inférieure), le kth entre en jeu. Statistiquement, le temps il faut pour trouver le kième élément grandit avec n, O (n).
L'analyse des algorithmes complémentaires d'un programmeur donne une version qui est O (n), bien que l'auteur indique que le facteur constant est si élevé , vous préféreriez probablement la méthode naïve de tri-liste, puis de sélection.
J'ai répondu à la lettre de votre question:)
La bibliothèque standard C ++ a presque exactement cette fonction appeler nth_element , bien que cela modifie vos données. Il a prévu un temps d'exécution linéaire, O (N), et effectue également un tri partiel.
const int N = ...;
double a[N];
// ...
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a
Bien que vous ne soyez pas très sûr de la complexité de O (n), vous serez sûrement compris entre O (n) et nLog (n). Assurez-vous également d'être plus proche de O (n) que nLog (n). La fonction est écrite en Java
public int quickSelect(ArrayList<Integer>list, int nthSmallest){
//Choose random number in range of 0 to array length
Random random = new Random();
//This will give random number which is not greater than length - 1
int pivotIndex = random.nextInt(list.size() - 1);
int pivot = list.get(pivotIndex);
ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();
//Split list into two.
//Value smaller than pivot should go to smallerNumberList
//Value greater than pivot should go to greaterNumberList
//Do nothing for value which is equal to pivot
for(int i=0; i<list.size(); i++){
if(list.get(i)<pivot){
smallerNumberList.add(list.get(i));
}
else if(list.get(i)>pivot){
greaterNumberList.add(list.get(i));
}
else{
//Do nothing
}
}
//If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list
if(nthSmallest < smallerNumberList.size()){
return quickSelect(smallerNumberList, nthSmallest);
}
//If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
//The step is bit tricky. If confusing, please see the above loop once again for clarification.
else if(nthSmallest > (list.size() - greaterNumberList.size())){
//nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in
//smallerNumberList
nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
return quickSelect(greaterNumberList,nthSmallest);
}
else{
return pivot;
}
}
J'ai mis au point la recherche du kth minimum avec n éléments non triés à l’aide de la programmation dynamique, en particulier de la méthode tournoi. Le temps d'exécution est O (n + klog (n)). Le mécanisme utilisé est répertorié comme l'une des méthodes de la page Wikipedia sur l'algorithme de sélection (comme indiqué dans l'un des messages ci-dessus). Vous pouvez en savoir plus sur l’algorithme et trouver du code (java) sur la page de mon blog Recherche du kth minimum . De plus, la logique peut effectuer un classement partiel de la liste - renvoie le premier K min (ou max) dans le temps O (klog (n)).
Bien que le code fourni donne le kth minimum, une logique similaire peut être utilisée pour trouver le kth maximum dans O (klog (n)), en ignorant le travail préalable à la création d'un arbre de tournoi.
Vous pouvez le faire dans O (n + kn) = O (n) (pour une constante k) pour le temps et pour O (k) pour un espace, en gardant une trace des k plus gros éléments que vous avez vus.
Pour chaque élément du tableau, vous pouvez parcourir la liste des k plus grands et remplacer le plus petit des éléments par le nouveau s'il est plus grand.
La solution de pile prioritaire de Warren est plus nette cependant.
Sélection rapide sexy en Python
def quickselect(arr, k):
'''
k = 1 returns first element in ascending order.
can be easily modified to return first element in descending order
'''
r = random.randrange(0, len(arr))
a1 = [i for i in arr if i < arr[r]] '''partition'''
a2 = [i for i in arr if i > arr[r]]
if k <= len(a1):
return quickselect(a1, k)
elif k > len(arr)-len(a2):
return quickselect(a2, k - (len(arr) - len(a2)))
else:
return arr[r]
Recherchez la médiane du tableau en temps linéaire, puis utilisez la procédure de partition exactement comme dans le tri rapide pour diviser le tableau en deux parties, les valeurs à gauche de la médiane étant inférieures (<) à celles de la médiane et au juste supérieur à la médiane (>), cela aussi peut être fait en temps linéaire, maintenant, allez à la partie du tableau où se trouve le kième élément, Maintenant, la récurrence devient: T (n) = T (n / 2) + cn ce qui me donne O (n) global.
Vous trouverez ci-dessous le lien vers la mise en œuvre complète avec une explication assez détaillée du fonctionnement de l’algorithme de recherche du Kth élément dans un algorithme non trié. L'idée de base est de partitionner le tableau comme dans QuickSort. Toutefois, afin d'éviter les cas extrêmes (par exemple, lorsque le plus petit élément est choisi comme pivot à chaque étape, de sorte que l'algorithme dégénère en temps d'exécution O (n ^ 2)), une sélection de pivot spéciale est appliquée, appelée algorithme de médiane de médiane. L’ensemble de la solution s’exécute en un temps O (n) dans les cas les plus graves et les plus graves.
Voici un lien vers l'article complet (il s'agit de trouver le Kth plus petit élément, mais le principe est le même pour trouver le Kth le plus grand ):
Selon ce document, Trouver le Kth élément le plus important dans une liste de n éléments l'algorithme suivant prendra O(n) du temps dans le pire des cas.
- Divisez le tableau en n / 5 listes de 5 éléments chacune.
- Trouvez la médiane dans chaque sous-tableau de 5 éléments.
- Récursivement & # 64257; Trouvez la médiane de toutes les médianes, appelons-le M
- Partitionnez le tableau en deux sous-tableaux Le premier sous-tableau contient les éléments plus grands que M, disons que ce sous-tableau est a1, alors que les autres sous-tableaux contiennent les éléments plus petits que M., appelons ce sous-tableau a2.
- Si k < = | a1 |, retourne la sélection (a1, k).
- Si k & # 8722; 1 = | a1 |, retourne M.
- Si k > | a1 | + 1, retourne la sélection (a2, k & # 8722; a1 & # 8722; 1).
Analyse: Comme suggéré dans le document d'origine:
Nous utilisons la médiane pour partitionner la liste en deux moitiés (la première moitié, si
k <= n/2, et la seconde moitié sinon). Cet algorithme prend tempscnau premier niveau de récursion pour une constantec,cn/2à au niveau suivant (puisque nous recourrons dans une liste de taille n / 2),cn/4à la troisième niveau, et ainsi de suite. Le temps total pris estcn + cn/2 + cn/4 + .... = 2cn = o(n).
Pourquoi la taille de la partition est prise 5 et non 3?
Comme mentionné dans le document d'origine:
En divisant la liste par 5, on obtient une division dans le pire des cas de 70 & # 8722; 30. Au moins la moitié des médianes plus grandes que la médiane des médianes, donc au moins la moitié des n / 5 blocs ont au moins 3 éléments, ce qui donne une
3n/10split, ce qui signifie que l’autre partition a 7n / 10 dans le pire des cas. Cela donneT(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1, le Le temps d'exécution le plus défavorable estO(nlogn).
Maintenant, j'ai essayé d'implémenter l'algorithme ci-dessus en tant que:
public static int findKthLargestUsingMedian(Integer[] array, int k) {
// Step 1: Divide the list into n/5 lists of 5 element each.
int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
// Step 2: Find pivotal element aka median of medians.
int medianOfMedian = findMedianOfMedians(array, noOfRequiredLists);
//Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
for (Integer element : array) {
if (element < medianOfMedian) {
listWithSmallerNumbers.add(element);
} else if (element > medianOfMedian) {
listWithGreaterNumbers.add(element);
}
}
// Next step.
if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
return -1;
}
public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
int[] medians = new int[noOfRequiredLists];
for (int count = 0; count < noOfRequiredLists; count++) {
int startOfPartialArray = 5 * count;
int endOfPartialArray = startOfPartialArray + 5;
Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
// Step 2: Find median of each of these sublists.
int medianIndex = partialArray.length/2;
medians[count] = partialArray[medianIndex];
}
// Step 3: Find median of the medians.
return medians[medians.length / 2];
}
Juste pour compléter, un autre algorithme utilise la file d'attente prioritaire et prend du temps 18
18.
public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
int p = 0;
int numElements = nums.length;
// create priority queue where all the elements of nums will be stored
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// place all the elements of the array to this priority queue
for (int n : nums) {
pq.add(n);
}
// extract the kth largest element
while (numElements - k + 1 > 0) {
p = pq.poll();
k++;
}
return p;
}
Ces deux algorithmes peuvent être testés comme suit:
public static void main(String[] args) throws IOException {
Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
System.out.println(findKthLargestUsingMedian(numbers, 8));
System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
}
Comme prévu, la sortie est la suivante: <=>
Qu'en est-il de cette approche un peu
Conservez un buffer of length k et un tmp_max, obtenir tmp_max vaut O (k) et est effectué n fois afin que quelque chose comme O(kn)
Est-ce exact ou manque-t-il quelque chose?
Bien qu’elle ne bat pas le cas moyen de la méthode quickselect ni le cas le plus défavorable de la méthode des statistiques médianes, elle est assez facile à comprendre et à mettre en œuvre.
parcourir la liste. si la valeur actuelle est supérieure à la plus grande valeur stockée, enregistrez-la en tant que valeur la plus grande et supprimez les valeurs 1-4 et 5 supprimées de la liste. Sinon, comparez-le au numéro 2 et faites la même chose. Répétez l'opération en la comparant à toutes les 5 valeurs stockées. cela devrait le faire dans O (n)
je voudrais suggérer une réponse
si nous prenons les k premiers éléments et les trions dans une liste chaînée de k valeurs
maintenant pour chaque autre valeur, même dans le pire des cas, si nous effectuons un tri par insertion pour les valeurs restantes, même dans le pire des cas, le nombre de comparaisons sera k * (nk) et pour les valeurs précédentes à trier, il sera k * (k-1) donc il en résulte (nk-k) qui est o (n)
acclamations
L’explication de l’algorithme de médiane - de - médian permettant de trouver le k-ème plus grand nombre entier sur n peut être trouvée ici: http://cs.indstate.edu/~spitla/presentation.pdf
L'implémentation en c ++ est la suivante:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMedian(vector<int> vec){
// Find median of a vector
int median;
size_t size = vec.size();
median = vec[(size/2)];
return median;
}
int findMedianOfMedians(vector<vector<int> > values){
vector<int> medians;
for (int i = 0; i < values.size(); i++) {
int m = findMedian(values[i]);
medians.push_back(m);
}
return findMedian(medians);
}
void selectionByMedianOfMedians(const vector<int> values, int k){
// Divide the list into n/5 lists of 5 elements each
vector<vector<int> > vec2D;
int count = 0;
while (count != values.size()) {
int countRow = 0;
vector<int> row;
while ((countRow < 5) && (count < values.size())) {
row.push_back(values[count]);
count++;
countRow++;
}
vec2D.push_back(row);
}
cout<<endl<<endl<<"Printing 2D vector : "<<endl;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
cout<<vec2D[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
// Calculating a new pivot for making splits
int m = findMedianOfMedians(vec2D);
cout<<"Median of medians is : "<<m<<endl;
// Partition the list into unique elements larger than 'm' (call this sublist L1) and
// those smaller them 'm' (call this sublist L2)
vector<int> L1, L2;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
if (vec2D[i][j] > m) {
L1.push_back(vec2D[i][j]);
}else if (vec2D[i][j] < m){
L2.push_back(vec2D[i][j]);
}
}
}
// Checking the splits as per the new pivot 'm'
cout<<endl<<"Printing L1 : "<<endl;
for (int i = 0; i < L1.size(); i++) {
cout<<L1[i]<<" ";
}
cout<<endl<<endl<<"Printing L2 : "<<endl;
for (int i = 0; i < L2.size(); i++) {
cout<<L2[i]<<" ";
}
// Recursive calls
if ((k - 1) == L1.size()) {
cout<<endl<<endl<<"Answer :"<<m;
}else if (k <= L1.size()) {
return selectionByMedianOfMedians(L1, k);
}else if (k > (L1.size() + 1)){
return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
}
}
int main()
{
int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
vector<int> vec(values, values + 25);
cout<<"The given array is : "<<endl;
for (int i = 0; i < vec.size(); i++) {
cout<<vec[i]<<" ";
}
selectionByMedianOfMedians(vec, 8);
return 0;
}
Il existe également un algorithme de sélection de Wirth , qui a une implémentation plus simple que QuickSelect. L'algorithme de sélection de Wirth est plus lent que QuickSelect, mais avec certaines améliorations, il devient plus rapide.
Plus en détail. En utilisant l'optimisation MODIFIND de Vladimir Zabrodsky et la sélection de pivot médiane sur 3 et en prêtant une attention particulière aux étapes finales de la partie partitionnement de l'algorithme, j'ai développé l'algorithme suivant (nommé de manière imaginable & «LefSelect quot;):
#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }
# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
int l=0, m = n-1, i=l, j=m;
float x;
while (l<m) {
if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
if( a[j] < a[k] ) F_SWAP(a[k],a[j]);
x=a[k];
while (j>k & i<k) {
do i++; while (a[i]<x);
do j--; while (a[j]>x);
F_SWAP(a[i],a[j]);
}
i++; j--;
if (j<k) {
while (a[i]<x) i++;
l=i; j=m;
}
if (k<i) {
while (x<a[j]) j--;
m=j; i=l;
}
}
return a[k];
}
Dans les tests de performance que j’ai ici , LefSelect a entre 20 et 30 ans % plus rapide que QuickSelect.
Solution Haskell:
kthElem index list = sort list !! index
withShape ~[] [] = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys
sort [] = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
where
ls = filter (< x)
rs = filter (>= x)
Ceci implémente la médiane des solutions médianes en utilisant la méthode withShape pour découvrir la taille d'une partition sans la calculer.
Voici une implémentation C ++ de Randomized QuickSelect. L'idée est de choisir au hasard un élément pivot. Pour implémenter une partition aléatoire, nous utilisons une fonction aléatoire, rand (), pour générer un index entre l et r, permuter l'élément à l'index généré aléatoirement avec le dernier élément et enfin appeler le processus de partition standard qui utilise le dernier élément comme pivot.
#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;
int randomPartition(int arr[], int l, int r);
// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of elements in array
if (k > 0 && k <= r - l + 1)
{
// Partition the array around a random element and
// get position of pivot element in sorted array
int pos = randomPartition(arr, l, r);
// If position is same as k
if (pos-l == k-1)
return arr[pos];
if (pos-l > k-1) // If position is more, recur for left subarray
return kthSmallest(arr, l, pos-1, k);
// Else recur for right subarray
return kthSmallest(arr, pos+1, r, k-pos+l-1);
}
// If k is more than number of elements in array
return INT_MAX;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// Standard partition process of QuickSort(). It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
{
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[r]); // swap the pivot
return i;
}
// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = rand() % n;
swap(&arr[l + pivot], &arr[r]);
return partition(arr, l, r);
}
// Driver program to test above methods
int main()
{
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = sizeof(arr)/sizeof(arr[0]), k = 3;
cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
return 0;
}
Le pire cas de complexité temporelle de la solution ci-dessus est toujours O (n2). Dans le pire des cas, la fonction randomisée peut toujours choisir un élément de coin. La complexité temporelle attendue de QuickSelect aléatoire ci-dessus est & # 920; (n)
- La file d'attente Priority est créée.
- Insérez tous les éléments dans le tas.
-
Appelez poll () k fois.
public static int getKthLargestElements(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>((x , y) -> (y-x)); //insert all the elements into heap for(int ele : arr) pq.offer(ele); // call poll() k times int i=0; while(i<k) { int result = pq.poll(); } return result; }
Ceci est une implémentation en Javascript.
Si vous libérez la contrainte que vous ne pouvez pas modifier le tableau, vous pouvez empêcher l'utilisation de mémoire supplémentaire à l'aide de deux index pour identifier la " partition actuelle " (dans un style de tri rapide classique - http: // www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/ ).
function kthMax(a, k){
var size = a.length;
var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2)
//Create an array with all element lower than the pivot and an array with all element higher than the pivot
var i, lowerArray = [], upperArray = [];
for (i = 0; i < size; i++){
var current = a[i];
if (current < pivot) {
lowerArray.push(current);
} else if (current > pivot) {
upperArray.push(current);
}
}
//Which one should I continue with?
if(k <= upperArray.length) {
//Upper
return kthMax(upperArray, k);
} else {
var newK = k - (size - lowerArray.length);
if (newK > 0) {
///Lower
return kthMax(lowerArray, newK);
} else {
//None ... it's the current pivot!
return pivot;
}
}
}
Si vous souhaitez tester son fonctionnement, vous pouvez utiliser cette variante:
function kthMax (a, k, logging) {
var comparisonCount = 0; //Number of comparison that the algorithm uses
var memoryCount = 0; //Number of integers in memory that the algorithm uses
var _log = logging;
if(k < 0 || k >= a.length) {
if (_log) console.log ("k is out of range");
return false;
}
function _kthmax(a, k){
var size = a.length;
var pivot = a[parseInt(Math.random()*size)];
if(_log) console.log("Inputs:", a, "size="+size, "k="+k, "pivot="+pivot);
// This should never happen. Just a nice check in this exercise
// if you are playing with the code to avoid never ending recursion
if(typeof pivot === "undefined") {
if (_log) console.log ("Ops...");
return false;
}
var i, lowerArray = [], upperArray = [];
for (i = 0; i < size; i++){
var current = a[i];
if (current < pivot) {
comparisonCount += 1;
memoryCount++;
lowerArray.push(current);
} else if (current > pivot) {
comparisonCount += 2;
memoryCount++;
upperArray.push(current);
}
}
if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);
if(k <= upperArray.length) {
comparisonCount += 1;
return _kthmax(upperArray, k);
} else if (k > size - lowerArray.length) {
comparisonCount += 2;
return _kthmax(lowerArray, k - (size - lowerArray.length));
} else {
comparisonCount += 2;
return pivot;
}
/*
* BTW, this is the logic for kthMin if we want to implement that... ;-)
*
if(k <= lowerArray.length) {
return kthMin(lowerArray, k);
} else if (k > size - upperArray.length) {
return kthMin(upperArray, k - (size - upperArray.length));
} else
return pivot;
*/
}
var result = _kthmax(a, k);
return {result: result, iterations: comparisonCount, memory: memoryCount};
}
Le reste du code consiste simplement à créer une aire de jeu:
function getRandomArray (n){
var ar = [];
for (var i = 0, l = n; i < l; i++) {
ar.push(Math.round(Math.random() * l))
}
return ar;
}
//Create a random array of 50 numbers
var ar = getRandomArray (50);
Maintenant, lancez vos tests plusieurs fois. En raison de Math.random (), il produira à chaque fois des résultats différents:
kthMax(ar, 2, true);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 2);
kthMax(ar, 34, true);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
kthMax(ar, 34);
Si vous le testez plusieurs fois, vous pouvez même voir de manière empirique que le nombre d'itérations est en moyenne de O (n) ~ = constant * n et que la valeur de k n'affecte pas l'algorithme.
Je suis venu avec cet algorithme et semble être O (n):
Disons que k = 3 et que nous voulons trouver le 3ème plus grand élément du tableau. Je créerais trois variables et comparerais chaque élément du tableau avec le minimum de ces trois variables. Si l'item du tableau est supérieur à notre minimum, nous remplacerons la variable min par la valeur de l'item. Nous continuons la même chose jusqu'à la fin du tableau. Le minimum de nos trois variables est le 3ème plus grand élément du tableau.
define variables a=0, b=0, c=0
iterate through the array items
find minimum a,b,c
if item > min then replace the min variable with item value
continue until end of array
the minimum of a,b,c is our answer
Et pour trouver le Kth élément le plus important, nous avons besoin de K variables.
Exemple: (k = 3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
Quelqu'un peut-il s'il vous plaît examiner cela et laissez-moi savoir ce que je manque?
Voici l'implémentation de l'algorithme eladv suggéré (je mets également ici l'implémentation à pivot aléatoire):
public class Median {
public static void main(String[] s) {
int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
System.out.println(selectK(test,8));
/*
int n = 100000000;
int[] test = new int[n];
for(int i=0; i<test.length; i++)
test[i] = (int)(Math.random()*test.length);
long start = System.currentTimeMillis();
random_selectK(test, test.length/2);
long end = System.currentTimeMillis();
System.out.println(end - start);
*/
}
public static int random_selectK(int[] a, int k) {
if(a.length <= 1)
return a[0];
int r = (int)(Math.random() * a.length);
int p = a[r];
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return random_selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return random_selectK(temp,k-small-equal);
}
}
public static int selectK(int[] a, int k) {
if(a.length <= 5) {
Arrays.sort(a);
return a[k-1];
}
int p = median_of_medians(a);
int small = 0, equal = 0, big = 0;
for(int i=0; i<a.length; i++) {
if(a[i] < p) small++;
else if(a[i] == p) equal++;
else if(a[i] > p) big++;
}
if(k <= small) {
int[] temp = new int[small];
for(int i=0, j=0; i<a.length; i++)
if(a[i] < p)
temp[j++] = a[i];
return selectK(temp, k);
}
else if (k <= small+equal)
return p;
else {
int[] temp = new int[big];
for(int i=0, j=0; i<a.length; i++)
if(a[i] > p)
temp[j++] = a[i];
return selectK(temp,k-small-equal);
}
}
private static int median_of_medians(int[] a) {
int[] b = new int[a.length/5];
int[] temp = new int[5];
for(int i=0; i<b.length; i++) {
for(int j=0; j<5; j++)
temp[j] = a[5*i + j];
Arrays.sort(temp);
b[i] = temp[2];
}
return selectK(b, b.length/2 + 1);
}
}
il est similaire à la stratégie quickSort, dans laquelle nous sélectionnons un pivot arbitraire et plaçons les éléments les plus petits à sa gauche et le plus grand à droite
public static int kthElInUnsortedList(List<int> list, int k)
{
if (list.Count == 1)
return list[0];
List<int> left = new List<int>();
List<int> right = new List<int>();
int pivotIndex = list.Count / 2;
int pivot = list[pivotIndex]; //arbitrary
for (int i = 0; i < list.Count && i != pivotIndex; i++)
{
int currentEl = list[i];
if (currentEl < pivot)
left.Add(currentEl);
else
right.Add(currentEl);
}
if (k == left.Count + 1)
return pivot;
if (left.Count < k)
return kthElInUnsortedList(right, k - left.Count - 1);
else
return kthElInUnsortedList(left, k);
}
Allez à la fin de ce lien: ...........
Vous pouvez trouver le k-ième élément le plus petit en O (n) temps et en espace constant. Si nous considérons que le tableau est uniquement pour les entiers.
L’approche consiste à effectuer une recherche binaire sur la plage de valeurs de tableau. Si nous avons une valeur min et une valeur max dans une plage entière, nous pouvons effectuer une recherche binaire sur cette plage. Nous pouvons écrire une fonction de comparaison qui nous dira si une valeur est la k-plus petite ou plus petite que la k-plus petite ou plus grande que la k-plus petite. Effectuez la recherche binaire jusqu’à atteindre le k-ème plus petit nombre
Voici le code pour cela
classe Solution:
def _iskthsmallest(self, A, val, k):
less_count, equal_count = 0, 0
for i in range(len(A)):
if A[i] == val: equal_count += 1
if A[i] < val: less_count += 1
if less_count >= k: return 1
if less_count + equal_count < k: return -1
return 0
def kthsmallest_binary(self, A, min_val, max_val, k):
if min_val == max_val:
return min_val
mid = (min_val + max_val)/2
iskthsmallest = self._iskthsmallest(A, mid, k)
if iskthsmallest == 0: return mid
if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
return self.kthsmallest_binary(A, mid+1, max_val, k)
# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
if not A: return 0
if k > len(A): return 0
min_val, max_val = min(A), max(A)
return self.kthsmallest_binary(A, min_val, max_val, k)
Il existe également un algorithme qui surpasse celui de la sélection rapide. Il s’appelle algorithme Floyd-Rivets (FR) .
Article original: https://doi.org/10.1145/360680.360694
Version téléchargeable: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108 & amp; rep = rep1 & amp; type = pdf
Article sur Wikipedia https://en.wikipedia.org/wiki/Floyd % E2% 80% 93algorithme_Rivest
J'ai essayé d'implémenter Quickselect et l'algorithme FR en C ++. De plus, je les ai comparées aux implémentations standard de la bibliothèque C ++ std :: nth_element (qui est essentiellement hybride introselect de quickselect et heapselect). Le résultat était quickselect et nth_element a fonctionné de manière comparable en moyenne, mais l'algorithme FR a fonctionné environ. deux fois plus vite comparé à eux.
Exemple de code que j'ai utilisé pour l'algorithme FR:
template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
if (n == 0)
return *(std::min_element(data.begin(), data.end()));
else if (n == data.size() - 1)
return *(std::max_element(data.begin(), data.end()));
else
return _FRselect(data, 0, data.size() - 1, n);
}
template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
size_t leftIdx = left;
size_t rightIdx = right;
while (rightIdx > leftIdx)
{
if (rightIdx - leftIdx > 600)
{
size_t range = rightIdx - leftIdx + 1;
long long i = n - (long long)leftIdx + 1;
long long z = log(range);
long long s = 0.5 * exp(2 * z / 3);
long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);
size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);
_FRselect(data, newLeft, newRight, n);
}
T t = data[n];
size_t i = leftIdx;
size_t j = rightIdx;
// arrange pivot and right index
std::swap(data[leftIdx], data[n]);
if (data[rightIdx] > t)
std::swap(data[rightIdx], data[leftIdx]);
while (i < j)
{
std::swap(data[i], data[j]);
++i; --j;
while (data[i] < t) ++i;
while (data[j] > t) --j;
}
if (data[leftIdx] == t)
std::swap(data[leftIdx], data[j]);
else
{
++j;
std::swap(data[j], data[rightIdx]);
}
// adjust left and right towards the boundaries of the subset
// containing the (k - left + 1)th smallest element
if (j <= n)
leftIdx = j + 1;
if (n <= j)
rightIdx = j - 1;
}
return data[leftIdx];
}
template <typename T>
int sgn(T val) {
return (T(0) < val) - (val < T(0));
}
Voici ce que je ferais:
initialize empty doubly linked list l
for each element e in array
if e larger than head(l)
make e the new head of l
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
Vous pouvez simplement stocker des pointeurs sur le premier et le dernier élément de la liste liée. Ils ne changent que lorsque les mises à jour de la liste sont effectuées.
Mise à jour:
initialize empty sorted tree l
for each element e in array
if e between head(l) and tail(l)
insert e into l // O(log k)
if size(l) > k
remove last element from l
the last element of l should now be the kth largest element
Tout d'abord, nous pouvons construire un fichier BST à partir d'un tableau non trié prenant O (n) en temps et à partir du fichier BST, nous pouvons trouver le kème plus petit élément de O (log (n)) qui, sur tout, compte pour un ordre de O (n). .
