Как найти k-й по величине элемент в несортированном массиве длины n в O (n)? - PullRequest
Новая
       159

Как найти k-й по величине элемент в несортированном массиве длины n в O (n)?

214 голосов
/ 31 октября 2008

Я считаю, что есть способ найти k-й по величине элемент в несортированном массиве длины n в O (n). Или, возможно, это «ожидаемый» O (N) или что-то. Как мы можем это сделать?

Ответы [ 31 ]

1 голос
/ 04 ноября 2014

Существует также Алгоритм выбора Вирта , который имеет более простую реализацию, чем QuickSelect. Алгоритм выбора Wirth медленнее, чем QuickSelect, но с некоторыми улучшениями он становится быстрее.

Более подробно. Используя оптимизацию MODIFIND для Владимира Забродского и выбор центральной оси 3 и уделив некоторое внимание последним шагам разделительной части алгоритма, я разработал следующий алгоритм (предположительно названный «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];
}

В тестах, которые я сделал здесь , LefSelect на 20-30% быстрее, чем QuickSelect.

0 голосов
/ 16 февраля 2018

Существует также один алгоритм, который превосходит алгоритм быстрого выбора. Он называется алгоритм Флойд-Ривец (FR) .

Оригинальный артикул: https://doi.org/10.1145/360680.360694

Загружаемая версия: 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

Я пытался реализовать быстрый выбор и алгоритм FR в C ++. Также я сравнил их со стандартными реализациями библиотеки C ++ std :: nth_element (который в основном представляет собой интроселектный гибрид quickselect и heapselect). Результатом был быстрый выбор, и nth_element работал в среднем сравнительно, но алгоритм FR работал ок. в два раза быстрее по сравнению с ними.

Пример кода, который я использовал для алгоритма 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));
}
0 голосов
/ 01 ноября 2017

Вы можете найти k-й наименьший элемент в O (n) времени и постоянном пространстве. Если мы рассмотрим массив только для целых чисел.

Подход состоит в том, чтобы выполнить бинарный поиск в диапазоне значений массива. Если у нас есть min_value и max_value в диапазоне целых чисел, мы можем выполнить двоичный поиск по этому диапазону. Мы можем написать функцию сравнения, которая сообщит нам, является ли любое значение kth-наименьшим или меньше kth-наименьшего или больше kth-наименьшего. Выполняйте двоичный поиск, пока не достигнете k-го наименьшего числа

Вот код для этого

класс Решение: 

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)
0 голосов
/ 25 июля 2016
0 голосов
/ 01 июля 2016

это похоже на стратегию быстрой сортировки, где мы выбираем произвольный стержень и выводим меньшие элементы слева и больше справа 

    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);
    }
0 голосов
/ 31 октября 2008

Что бы я сделал, это: 

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

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

Обновление: 

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
0 голосов
/ 02 июня 2016

Вот реализация предложенного алгоритма eladv (я также поместил здесь реализацию со случайным шарниром): 

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);
    }
}
0 голосов
/ 05 октября 2012

Для очень малых значений k (т.е. когда k << n), мы можем сделать это за ~ O (n) время. В противном случае, если k сравнимо с n, мы получим его в O (nlogn). </p>

0 голосов
/ 06 августа 2015

Я придумал этот алгоритм и, кажется, O (n):

Допустим, k = 3, и мы хотим найти третий по величине элемент в массиве. Я бы создал три переменные и сравнил бы каждый элемент массива с минимумом этих трех переменных. Если элемент массива больше нашего минимума, мы заменим переменную min значением элемента. Продолжаем то же самое до конца массива. Минимум наших трех переменных является третьим по величине элементом в массиве. 

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

И, чтобы найти K-й по величине элемент, нам нужно K переменных.

Пример: (k = 3) 

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

Может кто-нибудь проверить это и сообщить, что мне не хватает?

0 голосов
/ 17 сентября 2013

Сначала мы можем построить BST из несортированного массива, который занимает O (n) времени, а из BST мы можем найти k-й наименьший элемент в O (log (n)), который по всем показателям имеет порядок O (n). .

Страница:
...