LinkedList Min Max

JavaChild Membro desde: 21/02/2010 20:13:14 Mensagens: 140 Offline

Olá .. Estou precisando achar o valor min e mas em um LinkeList<object); sei que Collection resolve meu problema de achar o min e max se eu tiver <int>, <long>, etc... Mas não estou conseguindo chegar em uma solução para achar o min e max na seguinte situação.

Estou precisando achar o menor workload entre os objetos Task armazenados em minha Lista. Alguem poderia me adjuar??

até

GUJ Expert Membro desde: 22/03/2005 20:57:48 Mensagens: 3420 Offline

spiderman wrote:Olá .. Estou precisando achar o valor min e mas em um LinkeList<object); sei que Collection resolve meu problema de achar o min e max se eu tiver <int>, <long>, etc... Mas não estou conseguindo chegar em uma solução para achar o min e max na seguinte situação.

O problema de usar list é que podem haver mais do que um minimo ou mais do que um máximo.

Na realidade linkedlist não é a melhor opção aqui.

Primeiro ordene a lista usando um comparator que compara o tamanho das tasks.
Os extremos serão agora o minimo e o máximo. Vc pega o ultimo item e o primeiro.
Depois compara com os items imediatamente a seguir e se forem iguais vc tem que decidir qual quer.

Se vc tem a garantia de que apenas existe um máximo e um minimo, ou que , havendo vários qq um serve, então é melhor usar TreeSet
Esta classe faz as contas para vc e imediatemante lhe retorna os máximos e minimo usando last() e first()

This message was edited 2 times. Last update was at 19/03/2010 11:27:29

Classes:

import java.util.LinkedList;

public class MainClass {

LinkedList<Task> lista;
    Task job;

MainClass() {
        // TODO Auto-generated method stub
        lista = new LinkedList<Task>();
        Task taskMin;
        int x = 0;

for (int i = 0; i < 10; i++) {
            x = i + 5;
            job = new Task();
            job.setWorkload(x);
            lista.add(job);
        }
    }

public int encontrarMenorValor(){
        int retorno = Integer.MAX_VALUE;
        for (int i = 0; i < lista.size(); i++) {
            if(retorno > lista.get(i).getWorkload()){
                retorno = lista.get(i).getWorkload();
            }
        }
        return retorno;
    }

public int encontrarMaiorValor(){
        int retorno = 0;
        for (int i = 0; i < lista.size(); i++) {
            if(retorno < lista.get(i).getWorkload()){
                retorno = lista.get(i).getWorkload();
            }
        }
        return retorno;
    }

public void imprimeLista() {
        for (int i = 0; i < lista.size(); i++) {
            System.out.println(lista.get(i).getWorkload());
        }
    }

public static void main(String[] args) {
        MainClass mainClass = new MainClass();
        mainClass.imprimeLista();
        System.out.println("Menor: "+mainClass.encontrarMenorValor());
        System.out.println("Maior: "+mainClass.encontrarMaiorValor());
    }
}

class Task {

int workload = 0;

public Task() {
    }

public void setWorkload(int workload) {
        this.workload = workload;
    }

public int getWorkload() {
        return workload;
    }
}

Espero ter ajudado!

Abraço!

This message was edited 1 time. Last update was at 19/03/2010 11:33:14

sergiotaborda wrote:
Primeiro ordene a lista usando um comparator que compara o tamanho das tasks.
Os extremos serão agora o minimo e o máximo. Vc pega o ultimo item e o primeiro.
Depois compara com os items imediatamente a seguir e se forem iguais vc tem que decidir qual quer.

Se vc tem a garantia de que apenas existe um máximo e um minimo, ou que , havendo vários qq um serve, então é melhor usar TreeSet
Esta classe faz as contas para vc e imediatemante lhe retorna os máximos e minimo usando last() e first()

Pode ser que eu não tenha entendido a dúvida do nosso amigo, mas não acho necessário fazer tudo isso só pra achar o min e o máx.

Se eu entendi errado, desconsiderem os meus posts acima.

Espero ter ajudado!

Abraço!

Virtual Machine Man Membro desde: 17/10/2006 14:17:21 Mensagens: 617 Offline

O método do Taborda evita todos esses métodos que você escreveu, acho mais prático, mas é um pouco mais complicado de "entender" á primeira vista...

Concordo que à primeira vista é mais complicado de "entender", mas se fosse uma lista bem grande, como ficaria o desempenho disso tudo pra ordenar?

Abraço!

JavaChild Membro desde: 21/02/2010 20:13:14 Mensagens: 140 Offline

Não sei se minha se eu estou correto, não cheguei a testar ainda mas me parece que o metodo do renanedpedroso está correto. Concordo com nosso amigo taborda, mas o meu problema é que não posso ordenar os elementos dessa lista, ou seja, tenho que manter a ordem de inserção.

t+-

Virtual Machine Man Membro desde: 17/10/2006 14:17:21 Mensagens: 617 Offline

spiderman wrote:Não sei se minha se eu estou correto, não cheguei a testar ainda mas me parece que o metodo do renanedpedroso está correto. Concordo com nosso amigo taborda, mas o meu problema é que não posso ordenar os elementos dessa lista, ou seja, tenho que manter a ordem de inserção.

t+-

Aí é um outro caso, e realmente o método do Taborda não seria ideal...

Voce poderia também criar sua própria classe implementando a interface List, e no método add() já verificar se este é o máximo ou o minimo... algo do tipo:

Exemplinho tosco, mas acho que deu pra entender o que eu tentei dizer...

This message was edited 1 time. Last update was at 19/03/2010 15:10:17

Essa maneira de guardar o min e max que o Marcelo mostrou é a mais otimizada de todas, pois você (futuramente) não precisará percorrer a lista em nenhum momento.

Marcelo, não achei o exemplo tosco não, muito pelo contrário quando 'bati o olho' nele já identifiquei qual era a idéia, isso é o que vale. hehehehe

Abraço!

Virtual Machine Man Membro desde: 17/10/2006 14:17:21 Mensagens: 617 Offline

renanedpedroso wrote:Essa maneira de guardar o min e max que o Marcelo mostrou é a mais otimizada de todas, pois você (futuramente) não precisará percorrer a lista em nenhum momento.

Marcelo, não achei o exemplo tosco não, muito pelo contrário quando 'bati o olho' nele já identifiquei qual era a idéia, isso é o que vale. hehehehe

Abraço!

Hehehe... é, a minha idéia foi personalizar a lista pro requisito dele... então, á cada novo objeto adicionado na List ele já valida o max e o min, sem precisar ficar fazendo mágica, nem iterações, etc etc... não sei se dá pra ficar melhor que isso... não pro caso dele, pelo menos...

This message was edited 1 time. Last update was at 19/03/2010 16:17:26

Exemplo do Marcelo é excelente. Faz 2n compatações, melhor que o O(nlogn) que ordenar gastaria, se for apenas esse o proposito. Podia tambem implementar Comparable e chamar Collections.min/max

Virtual Machine Man Membro desde: 17/10/2006 14:17:21 Mensagens: 617 Offline

Paulo Silveira wrote:Exemplo do Marcelo é excelente. Faz 2n compatações, melhor que o O(nlogn) que ordenar gastaria, se for apenas esse o proposito. Podia tambem implementar Comparable e chamar Collections.min/max

Eu pensei nisso também... aliás, muito bom receber elogios do cara que me ensinou a fazer isso... (fui seu aluno ai na Caelum, Paulo... faz teeeempo!

)

Notícias, artigos e o maior fórum brasileiro sobre Java