drugi najmniejszy element

0

Banalny problem. Napisalem program ktory wyswietli najmniejszy element tablicy, ale nie moge dojsc jak wyswietlic drugi co do wartosci najmniejszy element.
Czy moglby ktos mnie naprowadzic?

#include <iostream>
#include <cstdlib>
using namespace std;

int second(int array[], int number)
{
    int minimum = array[0];
    for(int i=0; i<number; i++)
    {
        if(minimum>array[i])
        minimum = i;
    }

    return minimum;
}

int main()
{
    int number;
    do
    {
        cin >> number;
    }
    while(number>999);
    int array[number];

    for(int index=0; index<number; index++)
    {
        array[index]=rand()%50;
    }

    for(int index=0; index<number; index++)
    {
        cout << index << " " << array[index] << endl;
    }

    int minimum = second(array,number);
    cout << endl << minimum << " " << array[minimum];

    return 0;
}
0

Dodaj dodatkową zmienną, np gtminimum, i trzymaj tam najmniejszy element większy od minimum,to będzie coś takiego:

if (array[i] < minimum)
{
    gtminimum = minimum;
    minimum = array[i]
}
if (array[i] > minumum and array[i] < gtminimum) gtminimum = array[i]
0

Albo po prostu posortuj tę tablicę i wybierz drugi element od końca/początku (jeśli istnieje).

1

Podczas przejścia przez tablicę zapisuj dwa największe elementy, a nie jeden. Tylko i aż tyle :).

0

Jeśli potrzebujesz rozwiązania, a nie ćwiczenia to

nth_element(tab, tab + 1, tab + sizeof(tab)/sizeof(*tab));
int second = tab[1];

Podobnie najmniejszy element można znaleźć

int min = *min_element(tab, tab + sizeof(tab)/sizeof(*tab));

Każda z tych funkcji działa w czasie O(n), czyli szybciej niż sortowanie.

0
twonek napisał(a):

Jeśli potrzebujesz rozwiązania, a nie ćwiczenia to

nth_element(tab, tab + 1, tab + sizeof(tab)/sizeof(*tab));
int second = tab[1];

Podobnie najmniejszy element można znaleźć

int min = *min_element(tab, tab + sizeof(tab)/sizeof(*tab));

Każda z tych funkcji działa w czasie O(n), czyli szybciej niż sortowanie.

nth_element ma zazwyczaj pesymistyczny czas O(n^2), O(n) jest złożonością oczekiwaną, zakładając, że używa zmodyfikowanego quicksorta partycjonującego tylko przedział zawierający szukany element (quickselect).

@RipvanWinkle
Jak musisz koniecznie napisać to samemu, zamiast użyć funkcji z biblioteki standardowej albo nie możesz zmienić kolejności elementów, to może to wyglądać tak:

int getSecondOrderStatistic(int array[], int number)
{
    assert(number >= 2 && "array too small");

    int first = array[0], second = array[1];
    if (second < first) {
        first = array[1];
        second = array[0];
    }

    for (int i = 2; i < number; i++) {
        if (array[i] < first) {
            second = first;
            first = array[i];
        } else if (array[i] < second) {
            second = array[i];
        }
    }

    return second;
}
0
nalik napisał(a):
twonek napisał(a):

Jeśli potrzebujesz rozwiązania, a nie ćwiczenia to

nth_element(tab, tab + 1, tab + sizeof(tab)/sizeof(*tab));
int second = tab[1];

Podobnie najmniejszy element można znaleźć

int min = *min_element(tab, tab + sizeof(tab)/sizeof(*tab));

Każda z tych funkcji działa w czasie O(n), czyli szybciej niż sortowanie.

Czy to przypadkiem nie sortuje i nie wypisuje 2 indexu tablicy? Tak to i ja umiem :D Chodzi o to, zeby wypisal bez sortowania index oraz wartosc 2 co do wartosci.
Ale sprawdze, moze sie myle.

nth_element ma zazwyczaj pesymistyczny czas O(n^2), O(n) jest złożonością oczekiwaną, zakładając, że używa zmodyfikowanego quicksorta partycjonującego tylko przedział zawierający szukany element (quickselect).

@RipvanWinkle
Jak musisz koniecznie napisać to samemu, zamiast użyć funkcji z biblioteki standardowej albo nie możesz zmienić kolejności elementów, to może to wyglądać tak:

int getSecondOrderStatistic(int array[], int number)
{
    assert(number >= 2 && "array too small");

    int first = array[0], second = array[1];
    if (second < first) {
        first = array[1];
        second = array[0];
    }

    for (int i = 2; i < number; i++) {
        if (array[i] < first) {
            second = first;
            first = array[i];
        } else if (array[i] < second) {
            second = array[i];
        }
    }

    return second;
}

Coś jest nie tak. Wypisuje zły wynik. Zaraz sprawdze co jest nie tak i moze uda mi sie poprawic :)

0

Czasami wyswietla dobre wyniki, czasami nie....

int second(int array[], int number)
{
    int minimum = array[0];
    int sec = array[1];
    for(int i=0; i<number; i++)
    {
        if(minimum>array[i])
        minimum = i;

        if(sec>array[i])
        sec!=minimum;
        sec = i;
    }
    return sec;
}
1
int second(int array[], int number)
{
     int a = std::min(array[0], array[1]);
     int b = std::max(array[0], array[1]);

     for (int i=2; i<number; ++i)
     {
          b = std::min(b, array[i]);
          if (a>b)
               std::swap(a, b);
     }
     return b;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0