БлогNot. Ищем k-ый по величине элемент в несортированном массиве за линейное время

Ищем k-ый по величине элемент в несортированном массиве за линейное время

Идея состоит в том, чтобы разделить массив на пятёрки элементов, которые будут сортироваться стандартным алгоритмом за время O(1).

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

Звучит довольно запутанно, но как-то вот так (листинг из консоли Visual Studio 2015):

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int findMedian(int arr[], int n) { //5 элементов сортируются быстро
 sort(arr, arr + n); return arr[n / 2];
}

static int cnt; //счетчик перестановок
void swp(int *a, int *b) { //перестановка a и b
 int t = *a; *a = *b; *b = t; cnt++;
}

int position(int arr[], int l, int r, int x) {
 //найти x в куске массива arr[l]..arr[r] и положить его в конец
 int i;
 for (i = l; i<r; i++) if (arr[i] == x) break;
 swp(&arr[i], &arr[r]);
 i = l;
 for (int j = l; j < r; j++) if (arr[j] <= x) {
  swp(&arr[i], &arr[j]); i++;
 }
 swp(&arr[i], &arr[r]);
 return i;
}

int kthItem(int arr[], int l, int r, int k) {
 int n = r - l + 1;
 if (k < 1 || k > n) return INT_MAX;
 int i, *med = new int[(n + 4) / 5];
 for (i = 0; i < n / 5; i++) med[i] = findMedian(arr + l + i * 5, 5);
 //ищем медианы из пятёрок элементов
 if (i * 5<n) { //хвост массива
  med[i] = findMedian(arr + l + i * 5, n % 5); i++;
 }
 int med2 = (i == 1 ? med[0] : kthItem(med, 0, i - 1, i / 2));
 //рекурсивно ищем медиану от найденных медиан
 int pos = position(arr, l, r, med2);
 if (pos - l == k - 1) return arr[pos];
 if (pos - l >  k - 1) return kthItem(arr, l, pos - 1, k);
 return kthItem(arr, pos + 1, r, k - pos + l - 1);
}

int main() {
 int arr[] = { 100, 50, 60, 40, 30, 10, 20, 80, 70, 90,
               120,140,150, 60, 90, 70, 35, 55, 75,300,
               59,58,57,56,55,54,53,52,51,50
  };
 int n = sizeof(arr) / sizeof(arr[0]),
  k = 3; //ищем k-й по величине, счёт с 1
 cout << k << "'th item is " << kthItem(arr, 0, n - 1, k);
 cout << endl << "Cnt=" << cnt << " for " << n << " item(s)";
 cin.get();
 return 0;
}

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

25.02.2019, 14:29 [1471 просмотр]


теги: c++ алгоритм

К этой статье пока нет комментариев, Ваш будет первым