Como encontrar o k-ésimo elemento maior em uma matriz não triados de comprimento n em O (n)?
https://stackoverflow.com/questions/251781
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu acredito que há uma maneira de encontrar o maior elemento k em uma matriz não ordenada de comprimento n em O (n). Ou talvez seja O (n) ou algo "esperado". Como podemos fazer isso?
Solução
Isso é chamado de encontrar o k-th ordem estatística . Há um algoritmo aleatório muito simples (chamado QuickSelect ) tendo tempo O(n) média, O(n^2) pior momento caso, e um algoritmo não-randomizado muito complicado (chamado introselect ), tendo O(n) pior caso Tempo. Há algumas informações sobre Wikipedia , mas não é muito bom.
Tudo o que você precisa está em estes powerpoint slides de . Só para extrair o algoritmo básico do algoritmo O(n) pior caso (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)
É também muito bem detalhado na Introdução aos Algoritmos livro de Cormen et al.
Outras dicas
Se você quer um algoritmo O(n) verdade, ao contrário de O(kn) ou algo assim, então você deve usar QuickSelect (que é basicamente quicksort onde você joga fora a partição que você não está interessado em). Meu prof tem um grande writeup, com a análise de tempo de execução: ( referência )
O QuickSelect algoritmo encontra rapidamente o k-th menor elemento de uma matriz não ordenada de elementos n. É um RandomizedAlgorithm , então calculamos o pior caso de esperado tempo de execução.
Aqui é o algoritmo.
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
O que é o tempo de execução deste algoritmo? Se o adversário vira as moedas para nós, podemos descobrir que o pivô é sempre o maior elemento e k é sempre 1, dando um tempo de execução de
T(n) = Theta(n) + T(n-1) = Theta(n2)Mas se as escolhas são de fato aleatório, o tempo de execução esperado é dado por
T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1)) onde estamos fazendo a suposição não é totalmente razoável de que a recursão sempre cai na maior de A1 ou A2.
Vamos palpite de que T(n) <= an por algum a. Então, temos
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 e agora de alguma forma temos que obter a soma horrendo à direita do sinal de mais para absorver o cn à esquerda. Se nós apenas envolveram como 2(1/n) ∑i=n/2 to n an, temos aproximadamente 2(1/n)(n/2)an = an. Mas isso é muito grande - não há espaço para espremer em um cn extra. Então, vamos expandir a soma usando a fórmula da série aritmética:
∑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 onde tomamos vantagem de n ser "suficientemente grande" para substituir os fatores floor(n/2) feios com o muito mais limpa (e menores) n/4. Agora podemos continuar com
cn + 2 (1/n) ∑i=floor(n/2) to n ai,
<= cn + (2a/n) (15/32) n2
= n (c + (15/16)a)
<= an desde a > 16c.
Isto dá T(n) = O(n). É claramente Omega(n), então temos T(n) = Theta(n).
A rápida no Google sobre isso ( 'k maior variedade elemento') retornou este: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17
"Make one pass through tracking the three largest values so far."
(era especificamente para 3d maior)
e esta resposta:
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)
Você gosta quicksort. Escolha um elemento para tudo aleatório e empurrão maior ou menor. Neste ponto, você vai saber qual elemento você realmente pegou, e se ele é o elemento k estiver pronto, caso contrário você repetir com o bin (maior ou menor), que o elemento k iria cair. Estatisticamente falando, o tempo é preciso para encontrar o elemento k cresce com n, o (n).
Companion de um programador para análise de algoritmos dá uma versão que é o (n), embora o autor afirma que o fator constante é tão alto, você provavelmente preferiria o tipo-the-list-o então selecione método ingênuo.
Eu respondi a carta da sua pergunta:)
A biblioteca C ++ padrão tem quase exatamente que função de chamada nth_element, embora ele não modificar os seus dados. Tem esperado linear run-time, O (N), e ele também faz uma espécie parcial.
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
Apesar de não ser muito certo sobre O (n) a complexidade, mas terá a certeza de estar entre O (n) e NLog (n). Também certifique-se de estar mais perto de O (n) do que NLog (n). Função é escrito em 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;
}
}
Eu implementei encontrar k minimimum em n elementos não ordenados usando programação dinâmica, especificamente método torneio. O tempo de execução é O (n + klog (n)). O mecanismo utilizado está listada como um dos métodos em Wikipedia página sobre Selecção algoritmo (como indicado em uma de destacamento acima). Você pode ler sobre o algoritmo e também encontrar o código (Java) na minha página do blog Finding Kth mínima . Além disso, a lógica pode fazer ordenação parcial da lista -. Retorno primeiro min K (ou no máximo) em tempo O (klog (n))
Embora o mínimo k resultado código fornecido, uma lógica similar pode ser empregada para encontrar o máximo k em O (klog (n)), ignorando a pré-trabalho feito para criar árvore torneio.
Você pode fazê-lo em O (n + kn) = O (n) (para k constante) para o tempo e O (k) para o espaço, por manter o controle do k maiores elementos que você já viu.
Para cada elemento na matriz você pode verificar a lista de k maior e substituir o menor elemento com o novo se for maior.
solução montão prioridade de Warren é mais puro embora.
Sexy QuickSelect em 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]
Encontre a mediana da matriz em tempo linear, então use procedimento partição exatamente como no quicksort para dividir a matriz em duas partes, os valores para a esquerda da mediana menor (<) do que a mediana e ao direito maior do que ( >) médio, que também pode ser feito em tempo lineat, agora, ir a essa parte da matriz, onde mentiras elemento KTH, Agora recorrência torna-se: T (n) = T (n / 2) + cn o que me dá O (n) overal.
Abaixo está o link para a plena implementação com bastante uma extensa explicação sobre como o algoritmo para encontrar elemento Kth em um algoritmo funciona indiferenciados. idéia básica é particionar a matriz como em QuickSort. Mas a fim de evitar casos extremos (por exemplo, quando menor elemento é escolhido como pivô em cada passo, de modo que degenera algoritmo em tempo O (n ^ 2) correndo), selecção especial de articulação é aplicado, chamada algoritmo de mediana-de-medianas. Toda a solução é executado em O (n) em vez pior e em caso médio.
Aqui é o link para o artigo completo (é sobre encontrar Kth menor elemento, mas o princípio é o mesmo para encontrar Kth maior ):
De acordo com este documento Encontrar o Kth maior item em uma lista de itens n o seguinte algoritmo levará tempo O(n) no pior caso.
- Dividir a matriz em que n / 5 listas de 5 elementos cada.
- Encontre a mediana em cada sub conjunto de 5 elementos.
- Recursively fi nd a mediana de todas as medianas, vamos chamá-lo M
- Partition a matriz em duas sub variedade 1º sub-array contém os elementos maior do que M, digamos que este sub-matriz é a1, enquanto outros sub-array contém os elementos menores, em seguida M., vamos chamar este sub-array a2.
- Se k <= | a1 |., A seleção de retorno (a1, k)
- Se k-1 = | a1 |., Retorno M
- Se k> | a1 | + 1, selecção de retorno (a2, A1 k - 1) .
Análise: Como sugerido no artigo original:
Nós usamos a mediana para dividir a lista em duas metades (a primeira metade, se
k <= n/2, e a segunda metade de outra forma). Este algoritmo levacntempo no primeiro nível de recursão para algunscconstante,cn/2em o próximo nível (desde que recursividade em uma lista de tamanho n / 2), nocn/4terceiro nível, e assim por diante. O tempo total necessário écn + cn/2 + cn/4 + .... = 2cn = o(n).
Por tamanho da partição é tomada 5 e não 3?
Como mencionado no original papel :
Dividir a lista por 5 assegura uma divisão de pior caso de 70 - 30. Pelo menos metade das medianas maiores do que as medianas mediana de-, portanto, pelo menos metade dos n / 5 blocos têm pelo menos 3 elementos e isto dá um
3n/10divisão, o que significa que a outra partição é 7n / 10 no pior dos casos. Isso dáT(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1, o execução do pior caso isO(n)tempo.
Agora eu tenho tentado implementar o algoritmo acima como:
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];
}
Apenas por causa de conclusão, outro algoritmo faz uso de Priority Queue e leva O(nlogn) tempo.
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;
}
Ambos os algoritmos podem ser testados como:
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));
}
Como resultado esperado é:
18
18
Como sobre esta abordagem tipo
Mantenha uma buffer of length k e uma tmp_max, ficando tmp_max é O (k) e é feito n vezes para algo como O(kn)
É certo ou estou faltando alguma coisa?
Apesar de não vencer caso médio de QuickSelect e pior caso de método estatísticas mediana, mas a sua muito fácil de entender e implementar.
percorrer a lista. se o valor atual é maior que o maior valor armazenado, armazená-lo como o maior valor e bata com o baixo 1-4 e 5 gotas fora da lista. Se não, compará-lo com o número 2 e fazer a mesma coisa. Repita, verificando-lo contra todos os 5 valores armazenados. isso deve fazê-lo em O (n)
eu gostaria de sugerir uma resposta
Se tomarmos os primeiros k elementos e classificá-los em uma lista ligada de valores k
-se agora para qualquer outro valor, mesmo para o pior caso, se fizermos ordenação por inserção de valores nk descanso, mesmo no pior número de caso de comparações será k * (nk) e para valores prev K a ser ordenada que seja k * (k-1), de modo que vem a ser (NK-k), que é o (n)
aplausos
Explicação da mediana - de - medianas algoritmo para encontrar o k-th maior inteiro fora de n pode ser encontrada aqui: http://cs.indstate.edu/~spitla/presentation.pdf
implementação em C ++ está abaixo:
#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;
}
Há também de Wirth algoritmo de seleção, que tem uma implementação mais simples do que QuickSelect. algoritmo de seleção de Wirth é mais lento do que QuickSelect, mas com algumas melhorias torna-se mais rápido.
Em mais detalhes. Usando otimização MODIFIND de Vladimír Zábrodský ea seleção pivot mediana de-3 e pagar um pouco de atenção aos passos finais da parte divisora ??do algoritmo, eu tenho veio com o seguinte algoritmo (imaginably chamado "LefSelect"):
#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];
}
Em benchmarks que eu fiz aqui , LefSelect é 20-30 % mais rápido do que QuickSelect.
Haskell Solução:
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)
Este implementa a mediana de soluções medianas usando o método withShape para descobrir o tamanho de uma partição sem realmente calcular isso.
Aqui está uma implementação C ++ de Randomized QuickSelect. A ideia é a de escolher aleatoriamente um elemento pivô. Para implementar partição randomizado, usamos uma função aleatória, margem () para gerar índice de entre L e R, trocar o elemento no índice gerado aleatoriamente com o último elemento, e finalmente chamar o processo de partição padrão que utiliza último elemento como pivô.
#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;
}
O pior caso de tempo complexidade da solução acima ainda é O (n2) .Em pior dos casos, a função aleatorizado pode sempre escolher um elemento de canto. A complexidade de tempo esperado de acima randomizados QuickSelect é T (n)
- Tem fila de prioridade criado.
- Insira todos os elementos em heap.
-
poll Call () k vezes.
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; }
Esta é uma implementação em Javascript.
Se você soltar a restrição de que você não pode modificar a matriz, você pode evitar o uso de memória extra usando dois índices para identificar a "partição atual" (em estilo quicksort clássico - 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;
}
}
}
Se você quiser testar como executar, você pode usar esta variação:
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};
}
O resto do código é apenas para criar algum parque infantil:
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);
Agora, execute você testa um pouco tempo. Por causa da Math.random () que irá produzir cada vez que resultados diferentes:
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);
Se você testá-lo algumas vezes você pode ver ainda empiricamente que o número de iterações é, em média, O (n) ~ = constante * n eo valor de k não afeta o algoritmo.
Eu vim com esse algoritmo e parece ser O (n):
Vamos dizer k = 3 e queremos encontrar o terceiro maior item na matriz. Gostaria de criar três variáveis ??e comparar cada item da matriz com o mínimo de estas três variáveis. Se o item de matriz é maior do que o nosso mínimo, que iria substituir a variável min com o valor do item. Continuamos a mesma coisa até o final do array. O mínimo de nossas três variáveis ??é o 3º maior item na matriz.
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
E, para encontrar maior item Kth precisamos de variáveis ??k.
Exemplo: (k = 3)
[1,2,4,1,7,3,9,5,6,2,9,8]
Final variable values:
a=7 (answer)
b=8
c=9
Por favor alguém pode rever isso e deixe-me saber o que eu estou ausente?
Aqui está a implementação do eladv algoritmo sugeriu (eu também colocar aqui a implementação com pivot aleatório):
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);
}
}
é semelhante à estratégia QuickSort, onde nós escolher um pivô arbitrária, e trazer os elementos menores à sua esquerda, eo maior à direita
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);
}
Vá para o final deste link: ...........
Você pode encontrar o enésimo menor elemento em O (n) o tempo eo espaço constante. Se considerarmos a matriz é apenas para números inteiros.
A abordagem é fazer uma busca binária no intervalo de valores de matriz. Se temos um MIN_VALUE e uma MAX_VALUE tanto no intervalo inteiro, nós podemos fazer uma busca binária nessa gama. Nós podemos escrever uma função de comparação que nos dirá se algum valor é o k-menor ou menor do que k-menor ou maior do que k-menor. Faça a busca binária até chegar ao número k-menor
Aqui está o código para esse
Solução de classe:
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)
Há também um algoritmo, que o algoritmo Supera QuickSelect. É chamado Floyd-Rebites (FR) algoritmo .
Artigo original: https://doi.org/10.1145/360680.360694
versão descarregável: http: // citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf
https://en.wikipedia.org/wiki/Floyd % E2% 80% 93Rivest_algorithm
Eu tentei implementar QuickSelect e algoritmo de FR em C ++. Também I comparando-os com o padrão C ++ implementações biblioteca std :: nth_element (que é basicamente híbrido introselect de QuickSelect e heapselect). O resultado foi QuickSelect e correu nth_element comparavelmente em média, mas FR algoritmo correu aprox. duas vezes mais rápido em comparação com eles.
O código de exemplo que eu usei para o algoritmo 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));
}
O que eu faria é esta:
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
Você pode simplesmente armazenar ponteiros para o primeiro e último elemento da lista ligada. Eles só mudam quando atualizações na lista são feitas.
Update:
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
Em primeiro lugar, podemos construir uma BST da matriz de indiferenciados que leva tempo O (n) e do BST podemos encontrar o enésimo menor elemento em O (log (n)), que sobre todas as acusações a uma ordem de O (n) .
