Найти 3 самых больших числа в векторе

Question

Я пытаюсь сделать функцию, чтобы получить 3 самых больших числа в векторе.Например: Numbers: 1 6 2 5 3 7 4 Результат: 5 6 7

Я подумал, что могу отсортировать их DESC, получить 3 числа в начале и после этого прибегнуть к ним ASC, но это будеттрата памяти и времени выполнения.Я знаю, что есть более простое решение, но я не могу понять это.И еще одна проблема, что если у меня есть только два числа ...

Кстати: я использую в качестве компилятора BorlandC ++ 3.1 (я знаю, очень старый, но это то, что я буду использовать на экзамене ..)

Спасибо, ребята.

Л.Е .: Если кто-то хочет узнать больше о том, чего я пытаюсь достичь, вы можете проверить код:

#include<fstream.h>
#include<conio.h>

int v[1000], n;
ifstream f("bac.in");

void citire();
void afisare_a();
int ultima_cifra(int nr);
void sortare(int asc);

void main() {
    clrscr();
    citire();
    sortare(2);
    afisare_a();
    getch();
}

void citire() {
    f>>n;
    for(int i = 0; i < n; i++)
        f>>v[i];
        f.close();
}                            

void afisare_a() {
    for(int i = 0;i < n; i++)
            if(ultima_cifra(v[i]) == 5)
            cout<<v[i]<<" ";
}

int ultima_cifra(int nr) {
    return nr - 10 * ( nr / 10 );
}

void sortare(int asc) {
    int aux, s;
        if(asc == 1)
        do {
            s = 0;
            for(int i = 0; i < n-1; i++)
                if(v[i] > v[i+1]) {
                    aux = v[i];
                    v[i] = v[i+1];
                    v[i+1] = aux;
                    s = 1;
                }
        } while( s == 1);
    else
        do {
            s = 0;
            for(int i = 0; i < n-1; i++)
                if(v[i] < v[i+1]) {
                    aux = v[i];
                    v[i] = v[i+1];
                    v[i+1] = v[i];
                                        s = 1;
                }
                } while(s == 1);
}

Citire = Читать Afisare= Показать Ultima Cifra = Последняя цифра числа Сортар = Пузырьковая сортировка

Answer 1

Если бы вы использовали современный компилятор, вы могли бы использовать std::nth_element, чтобы найти первые три. Таким образом, вам придется сканировать массив, отслеживая три самых больших элемента, которые когда-либо были видны в любой момент времени, и когда вы доберетесь до конца, это будет ваш ответ.

Для трех элементов это тривиальная вещь для управления. Если вам нужно выполнить N самых больших (или самых маленьких) элементов, когда N может быть значительно больше, то вы почти наверняка захотите использовать алгоритм Хоара select, как и std::nth_element.

Answer 2

Вы можете сделать это без необходимости сортировки вообще, это выполнимо за O (n) время с линейным поиском и 3 переменными, сохраняющими ваши 3 самых больших числа (или индексы ваших самых больших чисел, если этот вектор не изменится).

Answer 3

Почему бы просто не пройти через него один раз и не отследить 3 встречающиеся старшие цифры?

РЕДАКТИРОВАТЬ: диапазон для ввода важен в том, как вы хотите отслеживать 3 старшие цифры.

Answer 4

Используйте std::partial_sort для сортировки по убыванию первых c элементов, которые вас интересуют.Он будет работать за линейное время для заданного количества желаемых элементов (n log c).

Answer 5

Если вы не можете использовать std :: nth_element, напишите свою собственную функцию выбора.

Вы можете прочитать о них здесь: http://en.wikipedia.org/wiki/Selection_algorithm#Selecting_k_smallest_or_largest_elements

Answer 6

Да, сортировка хороша.А особенно для длинных списков или списков переменной длины.

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

Answer 7

Сортируйте их как обычно, а затем итерируйте сзади, используя rbegin(), столько, сколько вы хотите извлечь (конечно, не дальше rend()).

sort будет иметь место, между прочим, ASC или DESC, поэтому память не является проблемой, так как ваш контейнерный элемент - int, поэтому не имеет собственной инкапсулированной памяти для управления.

Answer 8

Общее решение для верхних N элементов вектора:

1. Создание массива или вектора topElements длины N для ваших верхних N элементов.
2. Инициализируйте каждый элемент topElements значением первого элемента в вашем векторе.
3. Выберите следующий элемент в векторе или завершите, если не осталось элементов.
4. Есливыбранный элемент больше topElements[0], замените topElements[0] значением элемента.В противном случае перейдите к 3.
5. Начиная с i = 0, поменяйте topElements[i] на topElements[i + 1], если topElements[i] больше topElements[i + 1].
6. , а i -меньше N, с шагом i и переходом к 5.
7. Переход к 3.

Это должно привести к topElements, содержащему ваши главные N элементы в обратном порядкепорядок значений - то есть наибольшее значение в topElements[N - 1].

Answer 9

Следующее решение находит три самых больших числа в O (n) и сохраняет их относительный порядок:

std::vector<int>::iterator p = std::max_element(vec.begin(), vec.end());
int x = *p;
*p = std::numeric_limits<int>::min();

std::vector<int>::iterator q = std::max_element(vec.begin(), vec.end());
int y = *q;
*q = std::numeric_limits<int>::min();

int z = *std::max_element(vec.begin(), vec.end());

*q = y;   // restore original value
*p = x;   // restore original value

Answer 10

Спасибо @ nevets1219 за указание, что приведенный ниже код имеет дело только с положительными числами.

Я недостаточно тестировал этот код, но это начало:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> nums;
    nums.push_back(1);
    nums.push_back(6);
    nums.push_back(2);
    nums.push_back(5);
    nums.push_back(3);
    nums.push_back(7);
    nums.push_back(4);

    int first = 0;
    int second = 0;
    int third = 0;

    for (int i = 0; i < nums.size(); i++)
    {
        if (nums.at(i) > first)
        {
            third = second;
            second = first;            
            first = nums.at(i);
        }
        else if (nums.at(i) > second)
        {
            third = second;
            second = nums.at(i);
        }
        else if (nums.at(i) > third)
        {
            third = nums.at(i);
        }
        std::cout << "1st: " << first << " 2nd: " << second << " 3rd: " << third << std::endl;

    }

    return 0;
}