проблема выбора алгоритма

Question

Предположим, у вас есть массив A из n элементов, и вы хотите найти k элементов в A ближайших к медиане A. Например, если A содержит 9 значений {7, 14, 10, 12, 2, 11, 29, 3, 4} и k = 5, тогда ответом будут значения {7, 14, 10, 12, 11}, так как медиана равно 10, и это пять значений в A, ближайший к значению 10. Дайте алгоритм решить эту проблему за O (n) раз.

Я знаю, что алгоритм выбора (глубокий выбор) является подходящим алгоритмом для этой задачи, но я думаю, что он будет выполняться за O (n * logn) времени вместо O (n). Любая помощь будет принята с благодарностью:)

Answer 1

Сначала вам нужно будет найти медиану, что можно сделать в O(n) (например, с использованием алгоритма Hoare's Quickselect ).

Затем вам нужно будет реализовать алгоритм сортировкикоторый сортирует элементы в массиве в соответствии с их абсолютным расстоянием до медианы (сначала наименьшее расстояние).

Если бы вы отсортировали весь массив таким образом, это обычно занимало бы от O(n * log n) до * 1009.* в зависимости от используемого алгоритма.Однако, поскольку вам нужны только первые k значения, сложность может быть уменьшена до O(k * log n) до O(k * n).

Поскольку k является константой и не зависит от размера массива,общая сложность в худшем случае составит: O(n) (для поиска медианы) + O(k * n) (сортировка), что составляет O(n) в целом.

Answer 2

Предположение: мы заботимся о значениях k в A, которые являются ближайшими к медиане. Если бы у нас было A = {1,2,2,2,2,2,2,2,2,2,2,2,3} и k = 3, ответ равен {2,2,2}. Аналогично, если у нас A = {0,1,2,3,3,4,5,6} и k = 3, ответы {2,3,3} и {3,3,4} одинаково действительны. Кроме того, нас не интересуют индексы, из которых получены эти значения, хотя я предполагаю, что некоторые небольшие изменения в алгоритме сработают.

1. Как утверждает Гродригес, сначала найдите медиану за O (n) времени. Пока мы это делаем, следите за самым большим и самым маленьким числом
2. Далее создайте массив K, длиной k элементов. Этот массив будет содержать расстояние, на которое элемент находится от медианы. (обратите внимание, что
3. Скопируйте первые k элементов из A в K.
4. Для каждого элемента A [i] сравните расстояние A [i] от медианы до каждого элемента K. Если A [i] ближе к медиане, чем самый дальний элемент из медианы в K, замените это вещь. В качестве оптимизации мы могли бы также отслеживать самые близкие и самые отдаленные элементы K по медиане, поэтому мы имеем более быстрое сравнение с K, или мы можем сохранить сортировку K, но ни одна оптимизация не требуется для работы за O (n) времени.

Псевдокод, 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.
  }
}

Answer 3

Я думаю, что вы можете сделать это, используя вариант быстрой сортировки.

Вы начинаете с набора S из n предметов и ищете "средние" k предметов.Вы можете думать об этом как о разбиении S на три части размеров n - k / 2 («нижние» элементы), k («средние» элементы) и n - k / 2 («верхние» элементы).

Это дает нам стратегию: сначала удалите нижние n - k / 2 предметов из S, оставив S '.Затем удалите верхние n - k / 2 элементов из S ', оставив S' ', который является средним k элементами S.

Вы можете легко разделить набор таким образом, используя "половину быстрой сортировки": выберитеось, разделите набор на L и U (нижний и верхний элементы относительно оси), тогда вы знаете, что элементы, которые нужно отбрасывать в разделе, должны быть либо полностью из L, а некоторые из U или наоборот: recurse соответственно.

[Если подумать, это может быть не совсем то, что вам нужно, если вы определили «ближе всего к медиане» каким-то другим способом, но это только начало.]