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;
}
0

A co jesli chce znalezc 3 najmniejszy element?

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