Supuesto: nos preocupamos por los valores de k en A que están más cerca de la mediana. Si tuviéramos un A = {1,2,2,2,2,2,2,2,2,2,2,2,3}, y k = 3, la respuesta es {2,2,2}. De manera similar, si tenemos A = {0,1,2,3,3,4,5,6} yk = 3, las respuestas {2,3,3} y {3,3,4} son igualmente válidas. Además, no estamos interesados en los índices de los que provienen estos valores, aunque imagino que algunos pequeños ajustes al algoritmo funcionarían.
- Como estados de Grodrigues, primero encuentre la mediana en O (n) tiempo. Mientras estamos en eso, haga un seguimiento del número más grande y más pequeño
- A continuación, cree una matriz K, k elementos de largo. Esta matriz contendrá la distancia desde la mediana de un elemento.(Tenga en cuenta que
- Copie los primeros k elementos de A a K.
- Para cada elemento A [i], compare la distancia de A [i] desde la mediana con cada artículo de K. Si A [i] es más cerca de la mediana que el elemento más alejado de la mediana en K, reemplace ese elemento. Como optimización, también podríamos rastrear los artículos más cercanos y lejanos de K desde la mediana, por lo que tenemos una comparación más rápida con K o podríamos mantener K ordenada , pero ninguno de optimización es necesario operar en tiempo O (n)
Pseudocódigo, C++ ish:.
/* n = length of array
* array = A, given in the problem
* result is a pre-allocated array where the result will be placed
* k is the length of result
*
* returns
* 0 for success
* -1 for invalid input
* 1 for other errors
*
* Implementation note: optimizations are skipped.
*/
#define SUCCESS 0
#define INVALID_INPUT -1
#define ERROR 1
void find_k_closest(int n, int[] array, int k, int[] result)
{
// if we're looking for more results than possible,
// it's impossible to give a valid result.
if(k > n) return INVALID_INPUT;
// populate result with the first k elements of array.
for(int i=0; i<k; i++)
{
result[i] = array[i];
}
// if we're looking for n items of an n length array,
// we don't need to do any comparisons
// Up to this point, function is O(k). Worst case, k==n,
// and we're O(n)
if(k==n) return 0;
// Assume an O(n) median function
// Note that we don't bother finding the median if there's an
// error or if the output is the input.
int median = median(array);
// Convert the result array to be distance, not
// actual numbers
for(int i=0; i<k; i++)
{
result[i] = result[i]-median;
// if array[i]=1, median=3, array[i] will be set to 2.
// 4 3 -1.
}
// Up to this point, function is O(2k+n) = O(n)
// find the closest items.
// Outer loop is O(n * order_inner_loop)
// Inner loop is O(k)
// Thus outer loop is O(2k*n) = O(n)
// Note that we start at k, since the first k elements
// of array are already in result.
OUTER: for(int i=k; i<n; i++)
{
int distance = array[i]-median;
int abs_distance = abs(distance);
// find the result farthest from the median
int idx = 0;
#define FURTHER(a,b) ((abs(a)>abs(b)) ? 1 : 0;
INNER: for(int i=1; i<k; i++)
{
idx = (FURTHER(result[i],result[i-1])) ? i:i-1;
}
// If array[i] is closer to the median than the farthest element of
// result, replace the farthest element of result with array[i]
if(abs_distance < result[idx]){ result[idx] = distance; }
}
}
// Up to this point, function is O(2n)
// convert result from distance to values
for(int i=0; i<k; i++)
{
result[i] = median - result[i];
// if array[i]=2 , median=3, array[i] will be set to 1.
// -1 3 4.
}
}
OMI se tendrá que ordenar la lista, y eso siempre será más grande que O (n). – leppie
Su problema es equivalente a poder encontrar un percentil arbitrario en O (n) tiempo. Encontrar ** justo ** la mediana en el tiempo O (n) (es decir, resolver su problema para k = 1) es posible pero no trivial. El algoritmo probablemente podría extenderse para encontrar percentiles. ¿Por qué necesitas esto? ¿Es tarea? –
Dup: http://stackoverflow.com/questions/1557678/how-to-find-k-nearest-neighbors-to-the-median-of-n-distinct-numbers-in-on-time? – dfens