LinkedList Min Max

spiderman:

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 , , 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()

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!

sergiotaborda:

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. :oops:

Espero ter ajudado!

Abraço!

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!

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±

spiderman:

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...

public class TaskList implements List {
	
	private Task min;
	private Task max;

	public boolean add(Task task) {
		if ( task.getWorkload() < min.getWorkload() ) this.min = task;  
		if ( task.getWorkload() > max.getWorkload() ) this.max = task;
		return true;
	}

	public Task getMin() {
		return min;
	}

	public Task getMax() {
		return max;
	}

...

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

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!

renanedpedroso:

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…

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

Paulo Silveira:

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! :thumbup: )