Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Drugi najveci element u nizu

[es] :: Art of Programming :: Drugi najveci element u nizu

[ Pregleda: 3951 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

amel
Bosna

Član broj: 9063
Poruke: 43
*.informatik.tu-muenchen.de.



Profil

icon Drugi najveci element u nizu09.05.2006. u 13:31 - pre 217 meseci
Pozdrav, postoji li neki drugi i efikasniji nacin pronalazenja drugog najveceg elementa u nizu osim sljedecih mogucnosti

Mogucnost 1: Sortirati array a u opadajjucem nizu i izvaditi a[1]; (Mislim da je to sporo)
Mogucnost 2: Napisati funkciju "max" za pronalazenje najveceg elementa od array "a" i u drugoj funkciji secondMax ponovo napraviti pretrazivanje najveceg elementa bez koji nije jednak max.

Naime Mogucnost 2 bi u Java izgledala


IntArray:

Code:


public class IntArray {

    private int[] array;
    
    public IntArray(int length){
        this.array = new int[length];
    }
    
    public int get(int i){
        return this.array[i];
    }
    
    public void set(int i,int k){
        this.array[i] = k;
    }
    
    public int length(){
        return this.array.length;
    }
}


SecMaxInt:
Code:

public class secMaxInt extends IntArray{

    public secMaxInt(int length) {
        super(length);

    }

    public int max() {
        int c = this.get(0);
        for (int i = 1; i < this.length(); i++) {
            if (this.get(i) > c) {
                c = this.get(i)
            }
        }
        return c;
    }
    
    public int secmax() {
        
        int max = max();
        int secmax = 0;
        
        for (int i = 0; i < this.length(); i++) {
            if (this.get(i) > secmax && this.get(i) != max) {
                secmax = this.get(i);
            }
        }
        return secmax;        
    }
}



Postoji li kakav brzi algoritam osim drugog?

Scanner
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
193.198.17.*

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: Drugi najveci element u nizu09.05.2006. u 14:25 - pre 217 meseci
Batali Javu i sve će biti brže :D

Za velike nizove (recimo > 1000) će primjetno duže trajati sortiranje nego sekvencijalno traženje najvećeg elementa.

Najbolje bi bilo da jednom prolaziš po nizu i istovremeno pamtiš dva najveća elementa, umjesto dva prolaza što sad radiš.

[Ovu poruku je menjao cynique dana 09.05.2006. u 15:27 GMT+1]
 
Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
*.powernet.bg.

ICQ: 195487525
Sajt: cpptea.com


+1 Profil

icon Re: Drugi najveci element u nizu09.05.2006. u 16:13 - pre 217 meseci
Tako je, na pocetku trazis prva dva elementa niza koja se razlikuju po vrednosti i manji ti je secondMax a veci Max. Tada prolazis kroz ostale elemente. (1) Ako nadjes neki koji je veci od Max, tada secondMax postaje Max a Max postaje taj broj. (2) Ako pak nadjes broj koji je veci od secondMax ali manji Max, sexondMax dobija njegovu vrednost.

I pazi: drugi najveci moze da ne postoji: (1) kada niz ima manje od 2 elementa (2) jer su svi elementi u nizu jednaki.

F-ja nema garanciju. :p

Code:
    public static double solve(double arr[])
    {
        double smax,max;
        int i;
        
        // nepostojanje drugog najveceg: prazan niz
        // if(arr.length < 2) ...
        
        max = arr[0];
        smax = max;
        
        for(i=0;i<arr.length;i++)
        {
            if(arr[i]!=max)
            {
                if(arr[i]>max)
                {
                    smax = max;
                    max = arr[i];
                }
                else smax = arr[i];
                break;
            }
        }
        
        // nepostojanje drugog najveceg: svi elementi jednaki...
        // if(i == arr.length) ...
        
        i++;
        
        while(i<arr.length)
        {
            if(arr[i]>max)
            {
                smax = max;
                max = arr[i];
            }
            else if(arr[i]>smax && arr[i]<max)
            {
                smax = arr[i];
            }
            i++;
        }
        
        return smax;
    }


[Ovu poruku je menjao Mali Misha dana 09.05.2006. u 17:14 GMT+1]
Ipak se ++uje.
 
Odgovor na temu

kurt.hectic
Kurt Hectic

Član broj: 66049
Poruke: 25
*.etf.bg.ac.yu.



Profil

icon Re: Drugi najveci element u nizu09.05.2006. u 19:13 - pre 217 meseci
Postoji (u srednjem) brzi nacin. Potrazi na netu "k-th order statistics", koji se odnosi na computer science. (posto se isti pojam pojavljuje i na drugim mestima ali znaci drugo)
 
Odgovor na temu

cynique
Ivan Štambuk
Zagreb@Croatia

Član broj: 93690
Poruke: 155
193.198.17.*

ICQ: 106979934
Sajt: istambuk.blogspot.com


Profil

icon Re: Drugi najveci element u nizu10.05.2006. u 13:01 - pre 217 meseci
Sumnjam da nešto može biti brže od theta(n) koliko je sad..

BTW u C++ bi se drugi najveći element u kontejneru mogao vrlo trivijalno naći koristeći nth_element algoritam sa zagaranitranom prosječnom linearnom složenošću.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

template <class T>
inline void PRINT_ELEMENTS(const T& kol, const char* startstr = "", const char* endstr = "")
{
    std::cout << startstr;

    for( typename T::const_iterator iter = kol.begin(); iter != kol.end(); ++iter ) {
        std::cout << *iter << ' ';
    }
    std::cout << endstr;
    std::cout << endl;
}

int main(void)
{
    int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    vector<int> v( a, a + 10 );
    random_shuffle( v.begin(), v.end() );

    PRINT_ELEMENTS( v, "v = (", ")" );

    nth_element( v.begin(), v.begin()+1, v.end(), greater<int> () );

    PRINT_ELEMENTS( v, "v = (", ")" );

    return 0;
}


Zanimljivo da nth_element ne garantira da će podopsezi sa lijeve i desne strane n-tog elementa biti sortirani, a čini se da to oni uvijek jesu..
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.11.*



+1 Profil

icon Re: Drugi najveci element u nizu11.05.2006. u 01:30 - pre 217 meseci
Algoritam za nalazenje k-tog po velicini je slozenosti . Radi na slicno kao i QuickSort. O ovom algoritmu moze procitati na svakom mestu.
Math is like love. A simple idea but it can get complicated.
 
Odgovor na temu

amel
Bosna

Član broj: 9063
Poruke: 43
*.dip.t-dialin.net.



Profil

icon Re: Drugi najveci element u nizu12.05.2006. u 19:43 - pre 217 meseci
Jeste, sve je u redu, hvala, ali danas sam postavio jedno pitanje. Recimo da nam je dat array a[] ={1, 16, 16}. Algoritam od Malog Mishe i moj su OK, medjutim oni mi daje za rezultat 1 sto ne mora znaciti, a moze biti. Govorim iz tog razloga jer 16 moze isto biti drugi najveci element u nizu, je li tako? Zasto? Kad pogledamo malo neku oblast iz sporta i rang listu recimo

1.) xxxxxxx
xxxxx
xxx
4.) yyyyy

ovdje je i ovaj xxxxx drugi najveci. Sta vi mislite o tome?
Scanner
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: Drugi najveci element u nizu13.05.2006. u 10:41 - pre 217 meseci
stavi >= umjesto >
 
Odgovor na temu

[es] :: Art of Programming :: Drugi najveci element u nizu

[ Pregleda: 3951 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.