Медиана сложности медианов сложности

Question

Я реализовал алгоритм выбора nth_number с использованием медианов медиан. В wikipedia указано, что это сложность пространства O (1)

Мне пришлось хранить медианы во временном массиве, чтобы найти медианную среди этих медианов. Как бы вы могли это сделать, не используя лишнюю память? Если это не считается увеличением его пространственной сложности, объясните, пожалуйста.

function nth_number(v, n) { 
    var start = 0; 
    var end = v.length - 1; 
    var targetIndex = n - 1; 

    while(true) { 

     var medians = []; /* Extra memory. */ 

     /* Divide our array into groups of 5s. Find a median within each */ 
     for(var i = start; i <= end; i += 6) { 
      if(i + 5 < end) 
       medians.push(findMedian(v, i, i + 5)); 
      else 
       medians.push(findMedian(v, i, end)); 
     } 

     var median = findMedian(medians, 0, medians.length - 1); /* Find the median of all medians */ 

     var index = partition(v, median, start, end); 

     if(index === targetIndex) { 
      console.log(median); 
      return median; 
     } 
     else { 
      if(index < targetIndex) { 
       start = index + 1; 
       targetIndex -= index; 
      } 
      else { 
       end = index - 1; 
      } 
     } 
    } 
} 

Answer 1

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

Одна простая возможная стратегия состоит в том, чтобы чередовать группы из пяти, вместо того чтобы делать их последовательными. Таким образом, если вектор имеет N == 5K элементов, группы из пяти являются:

(0, k, 2k, 3k, 4k) 
(1, k+1, 2k+1, 3k+1, 4k+1) 
(2, k+2, 2k+2, 3k+2, 4k+2) 
... 
(k-1, 2k-1, 3k-1, 4k-1, 5k-1) 

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