Найти n-й самый маленький элемент в массиве без сортировки?

Question

Я хочу написать программу для поиска n-го наименьшего элемента без использования какой-либо техники сортировки.

Можем ли мы сделать это рекурсивно, разделить и победить стиль, как быструю сортировку?

Если нет, то как?

Answer 1

Вы можете найти информацию об этой проблеме здесь: Алгоритм выбора .

Answer 2

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

Вот как это работает:

• Как и в Quicksort, вы начинаете с выбора хорошего Pivot: то, что вы думаете, почти на полпути через ваш список. Затем вы просмотреть весь список предметов обмениваясь вещами взад и вперед, пока все предметы меньше, чем ваш опорный пункт находятся в начале списка, и все вещи больше твоего центра в конце. Ваш центр уходит в оставшееся место посередине.
• Обычно в быстрой сортировке вы бы рекурсировали по обе стороны от оси, но для Алгоритм выбора вы будете только рекурс на стороне, которая содержит индекс, который вас интересует. Итак, если Вы хотите найти третий самый низкий ценность, рекурс на любой стороне содержит индекс 2 (потому что индекс 0 1-е самое низкое значение).
• Вы можете прекратить повторение, когда вы сузил регион только до одного индекс. В конце у вас будет один несортированный список самых маленьких "m-1" объекты, и еще один несортированный список "n-m" крупнейших объекты. «М» -й объект будет промежуточным.

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

По-настоящему изящная вещь в этом заключается в том, что он обычно выполняется за O (n) времени. В первый раз он видит весь список. При первой рекурсии он видит около половины, затем одну четверть и т. Д. Итак, он просматривает около 2n элементов, поэтому он выполняется за O (n) времени. К сожалению, как и в случае быстрой сортировки, если вы последовательно выбираете плохую точку, вы будете работать за O (n ² ).

Answer 3

Вы можете использовать двоичную кучу, если не хотите использовать кучу Фибоначчи.

Algo:

1. Извлеките минимальную двоичную кучу из массива, эта операция займет время O (n).

2. Поскольку это минимальная двоичная куча, минимальным значением является элемент в корне.

3. Так что продолжайте удалять элемент из корня, пока не получите минимальное значение. o (1) операция

4. Убедитесь, что после каждого удаления вы заново сохраняете операцию heap kO (logn).

Итак, время выполнения здесь O (клогн) + O (n) ............ так что O (клогн) ...

Answer 4

Эту задачу вполне можно выполнить примерно за O(n) время (n - длина списка), используя структуру кучи (в частности, очередь с приоритетами основанный на куче Фибоначчи ), которая дает O(1) время вставки и O(log n) время удаления).

Рассмотрим задачу получения m-го наименьшего элемента из списка. Просто зацикливая список и добавляя каждый элемент в приоритетную очередь (размером m), вы можете эффективно создать очередь каждого из элементов в списке за O(n) время (или, возможно, меньше, используя некоторые оптимизации, хотя Я не уверен, что это чрезвычайно полезно). Затем достаточно просто удалить элемент с наименьшим приоритетом в очереди (наивысший приоритет - наименьший элемент), что занимает всего O(log m) времени, и все готово.

Таким образом, в целом временная сложность алгоритма будет O(n + log n), но, поскольку log n << n (то есть n растет намного быстрее, чем log n), это просто сокращается до O(n). Я не думаю, что вы сможете получить что-то значительно более эффективное, чем это в общем случае.

Answer 5

Самый простой способ найти n-й по величине элемент в массиве без использования методов сортировки.

public static void kthLargestElement() {
    int[] a = { 5, 4, 3, 2, 1, 9, 8 };
    int n = 3;
    int max = a[0], min = a[0];
    for (int i = 0; i < a.length; i++) {
        if (a[i] < min) {
            min = a[i];
        }
        if (a[i] > max) {
            max = a[i];
        }

    }

    int max1 = max, c = 0;
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a.length; j++) {
            if (a[j] > min && a[j] < max) {
                max = a[j];
            }
        }
        min = max;
        max = max1;
        c++;
        if (c == (a.length - n)) {
            System.out.println(min);
        }
    }
}

Answer 6

Here is the Ans to find Kth smallest element from an array:

#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
int Nthmin=0,j=0,i;
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall);
int main()
{
    int size;
    cout<<"Enter Size of array\n";
    cin>>size;
    int *arr=(int*)malloc(sizeof(int)*size);
    cout<<"\nEnter array elements\n";
    for(i=0;i<size;i++)
        cin>>*(arr+i);
    cout<<"\n";
    for(i=0;i<size;i++)
        cout<<*(arr+i)<<" ";
    cout<<"\n";
    int n=sizeof(arr)/sizeof(int);
    int result=GetNthSmall(arr,size,3);
    printf("Result = %d",result);
    getch();
    return 0;
}

int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall)
{
    int min=numbers[0];
    while(j<Nthsmall)
    {
        Nthmin=numbers[0];
        for(i=1;i<NoOfElements;i++)
        {
            if(j==0)
            {
                if(numbers[i]<min)
                {
                    min=numbers[i];
                }
                Nthmin=min;
            }
            else
            {
                if(numbers[i]<Nthmin && numbers[i]>min)
                    Nthmin=numbers[i];
            }
        }
        min=Nthmin;
        j++;
    }
    return Nthmin;
}

Answer 7

Таким образом можно использовать два стека, чтобы найти N-е наименьшее число за один проход.

• Начните с пустого стека A и стека B
• Нажмите первый номер в стек A-1006 *
• Следующее число вперед, выберите PUSH в стек A, только если номер меньше его вершины
• Когда вам нужно нажать на стек A, выполните следующие действия.
  • В то время как TOP стека-A больше нового номера, POP TOP стека-A и вставьте его в стек-B
  • Когда Stack-A становится пустым или его TOP меньше нового номера, НАЖМИТЕ на новый номер и восстановите содержимое Stack-B поверх него
  • В этот момент вы вставили новый номер в его правильное (отсортированное) место в стеке A, а стек B снова пуст
  • Если глубина стека-A теперь достаточна, вы достигли конца поиска

---

Я в целом согласен с оптимизационным анализом Нолдорина.
Это стековое решение направлено на простую схему, которая будет работать (с относительно большим перемещением данных - по двум стекам). Схема кучи уменьшает выборку для N-го наименьшего числа до обхода дерева (log m).

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

Решение стеков может быть сжато в требованиях к пространству путем реализации двух стеков в одном пространстве из K элементов (где K - размер вашего набора данных). Итак, недостатком является просто дополнительное движение стека при вставке.