Obtendo o maior valor de uma matriz

Como poderia fazer para obter o maior valor de uma matriz por exemplo:

int[] arr = {0,3,4,6,9,8,7,2,1,5}; //Maior valor de 'arr' é 9
Eis um exemplo:

Teria alguma função ou seria mais por meio de comparação mesmo?

A classe java.util.Arrays contém vários métodos sort(). Você pode classificar arrays de inteiros, doubles, longs e Object (entre outros tipos).

int[] i = { 8, 4, 12, 1 }; Arrays.sort(i); System.out.println(i[i.length-1]); // o maior valor...

Se quiser classificar objetos em uma ordem especifica, estude a interface Comparator.

essa é uma ótima solução, mas vc tem que tomar cuidado, pois ela modifica seu array, portanto se vc não quiser ele modificado ou vc faz um clone() ou usa outro método.

mas qqr metodo q seja vc vai ter q comparar os elementos, no meu ponto de vista o mais simples pra vc construir na mão é

Int[] array= {0,3,4,6,9,8,7,2,1,5};
Int maior= 0;
for (int i=0;i<array.length;i++){
   if (array[i]>maior) {maior=array[i];}
}

danieltaranta, a solução é boa para arrays pequenos…
uma alternativa seria:

int[] i = { 9, 8, 12, 1, 34 }; int[] x = new int[i.length]; System.arraycopy(i, 0, x, 0, i.length); Arrays.sort(x); System.out.println(x[x.length-1]); // o maior valor...

Quando vc não quiser modificar o array original e ele for muito grande para uma comparação direta, é melhor criar uma cópia desse array e odernar a cópia.

Um problema com o seu método, Daniel, é que ele itera sobre toda a Array de forma sequencial, e isso não é o que está ilustrado no OP.

Aqui vai um rabisco que talvez seja mais o que vc quer: :slight_smile:

	public static void main(String[] args) {
		int[] arr = { 0, 3, 4, 6, 9, 8, 7, 2, 1, 5 };
		System.out.println(max(arr, 0, 0));
	}

	public static int max(int[] array, int offset, int max) {
		if (array.length > offset + 1) {
			if (array[offset] > array[offset + 1])
				return max(
					array,
					offset + 1,
					array[offset] > max ? array[offset] : max);
			else
				return max(
					array,
					offset + 1,
					array[offset + 1] > max ? array[offset] : max);
		}
		return max;
	}

Pelo que eu sei o problema com a minha solução é q ela percorre todo o array, item por item. Mas um sort tb consulta cada elemento e tem q ordena-los, e pior, vc ainda tem q criar uma cópia, para modificar a cópia.

Pq isso seria melhor???

Fiquei curioso o fui pesquisar, achei o sequinte sobre o sort:

no caso o meu oferece uma performance de n, isso sem contar com o fato de ter q copiar o array.

Corrijam-me se estiver errado :?:

Se voce tem um array com ordem aleatoria, a melhor forma de pesquisa vai ser escrevendo 1 loop mesmo procurando pelo maior, como o daniel mostrou.
Caso voce queia saber os N maiores valores, construa 1 heap a partir do teu array e extraia o numero de elementos desejados, vai ser bem mais rapido que ordenar.

Se voce tem um array com ordem aleatoria, a melhor forma de pesquisa vai ser escrevendo 1 loop mesmo procurando pelo maior, como o daniel mostrou.
Caso voce queia saber os N maiores valores, construa 1 heap a partir do teu array e extraia o numero de elementos desejados, vai ser bem mais rapido que ordenar.

Voce leu errado, Daniel. Citando o texto por completo:

Ou seja, ele usa um quicksort modificado pra, no pior dos casos (um array já sortado), oferecer uma performance nlog(n), que não é nada mal perto de uma funcao quadratica, ja que p/ n = 1.000.000.000, nlog(n) = 20.723.265.836,946, e n**2 = 1.000.000.000.000.000.000. Nada mal mesmo. :smiley:

Ah, se vc quiser testar:

public static void main(String[] args) { long[] n = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; for (int i = 0; i < n.length; i++) { System.out.println("n: "+n[i]); System.out.println("O(n*log(n)): " + new DecimalFormat().format(n[i]*Math.log(n[i]))); System.out.println("O(n**2): " + new DecimalFormat().format(Math.pow(n[i], 2))); System.out.println(); } }

Rodar isso rende resultados bastante interessantes a partir da 4a iteracao :smiley:

Concordo q o sort do Java é melhor q o BoubleSort, esse sim é n^n.
Mas perai, eu sugeri um looping que passa apenas 1 vez pela matriz, isso não é n^n, é apenas n, mais rápido q n*log(n).

tô viajando?!?!?!?

Nao, nao tah nao Daniel - o louds está certo em dizer que se a intenção é meramente achar o maior número, o método mais rápido é iterar sobre toda a lista. Mas, se a idéia é sorting, os arrays do Java me surpreenderam com esse papo do O(n*log(n)) constante pro quicksort :slight_smile:

Não sabia que isso existia :smiley:

Tá certo, agora entendi, aconteceu uma discusão paralela a pergunta original, q queria apenas achar o maior.

Eu respondi para essa pergunta, mas li a discusão paralela sobre sort e pensei q era sobre a pergunta original tb!!! :smiley:

falando em ordenacao
se vc ta realmente preocupado com o caso ruim, use um algoritmo estavel de ordenacao, como mergesort ou headsort.
e se vc tiver conhecimento previo sobre a colecao utilize metodos que te rendem performance ainda melhor, como bucket ou radix sort, que podem executar em tempo O(n).

Quicksort puro ninguem usa de cara, oque o java 1.4.1, eh introsort, que eh feito quicksort, porem analisa 3, ate 9, numeros por passo para escolher o pivo e se o vetor for pequeno usa insertion sort.

Eu tinha montado uma solução parecida com essa:

int[] array= {0,3,4,6,9,8,7,2,1,5}; 
int maior= 0; 
for(int i=0;i<array.length;i++){
   if (array[i]>maior) {maior=array[i];} 
}

Só que não era muito prático percorrer um Array inteiro. E organizando um Array já tive problemas em que o 5 ficava na frente do 505, aí dava pau. Depois eu acabei achando esse código daqui:

import java.util.*;
public class max1 {
	public static void main(String args[])
	{
		Set hs = new HashSet();
		hs.add("1");
		hs.add("2");
		hs.add("3");
		hs.add("2");
  
		Iterator iter = hs.iterator();
		while (iter.hasNext()) {
			System.out.println(iter.next());
		}
  
		System.out.println("max = " + Collections.max(hs));
	}
}

É do site da Sun mesmo, só ainda não saquei pra que serve o HashSet, e o Collections.
Outra coisa, o livro ‘Java Como Programar 4a Edicao’ é bom??

uehuehuehuehue - isso me lembra que esqueci de “chutar” minha maquina ontem, antes de ir pra casa… :stuck_out_tongue:

Guilherme:

Se vc quer apenas saber qual o maior numero entre uma coleção de números com certeza um array é o menos viável, principalmente para uma quantidade muito grande de números.

No seu caso Quantos números ± vão existir :?:
Pq se forem poucos ainda acho q a solução q eu passei inicialmente é a melhor :!:

E outra coisa, vc precisa apenas saber o maior ou precisa ordernar os números :?:

Quanto a performance do HastMap em relação a outras Collections vou deixar para mentes mais experientes responderem, pois ainda não estudei muito alem da utilização básica :smiley:

Um HastMap é um Collection, assim como outras implementações de outras Estruturas de Dados.
Isso é material para muito estudo dependendo do quando vc quer se aprofundar nisso!

O livro Java Como Programar é um dos melhores, não conheço a 4ª edição, mas disem q é bem melhor q a 3ª. Na 3ª edição tem uma boa introdução a Collections, da pra aprender a usar legal.