Array algorithms: max, count, search, average
Tarefas comuns de array
- Algumas tarefas de array aparecem repetidamente: encontrar a soma, o maior, o menor, ou contar itens.
- Cada uma usa a mesma ideia: comece com um palpite, depois faça o loop e atualize.
- Esses padrões aparecem o tempo todo no exame AP CSA.
Soma e contagem
- Mantenha um total acumulado que comece em 0, e some cada valor.
- Para contar itens que passam em um teste, comece um contador em 0 e adicione 1 quando o teste for verdadeiro.
- Abaixo contamos quantos valores são pares (
v % 2 == 0).
public class Main {
public static void main(String[] args) {
int[] a = {3, 4, 7, 10};
int evens = 0;
for (int v : a) {
if (v % 2 == 0) {
evens = evens + 1;
}
}
System.out.println(evens); // 2
}
}
Encontrar o máximo
- Comece supondo que o primeiro valor é o maior:
int max = a[0];. - Faça o loop pelo resto. Se um valor for maior que
max, torne-o o novomax. - Isso funciona para números negativos também, porque o palpite vem do próprio array.
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int max = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] > max) {
max = a[i];
}
}
System.out.println(max); // 9
}
}
Encontrar o mínimo
- O mínimo usa a mesma estrutura — basta inverter o teste para
<. - Comece com
int min = a[0];e mantenha o menor valor que você vir. - Nunca inicie
minem 0; um valor real do array é uma boa primeira suposição.
public class Main {
public static void main(String[] args) {
int[] a = {3, 9, 2, 7};
int min = a[0];
for (int i = 1; i < a.length; i++) {
if (a[i] < min) {
min = a[i];
}
}
System.out.println(min); // 2
}
}
Buscar um valor
- Para encontrar onde um valor está, faça o loop do índice e compare cada elemento.
- Retorne o índice assim que encontrá-lo.
- Se o loop terminar sem correspondência, retorne
-1para significar "não encontrado".
public class Main {
public static void main(String[] args) {
int[] a = {5, 8, 13, 21};
int target = 13;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop at the first match
}
}
System.out.println(found); // 2
}
}
Média
- Média = soma dividida pela contagem. A contagem é
a.length. - Para obter um decimal, divida por
(double) a.length, para que a matemática não seja divisão inteira. (double)converte o comprimento em decimal antes da divisão.
public class Main {
public static void main(String[] args) {
int[] a = {2, 3, 10};
int total = 0;
for (int v : a) {
total = total + v;
}
double avg = total / (double) a.length;
System.out.println(avg); // 5.0
}
}
Erros comuns
- Comece um max ou min do primeiro elemento, depois compare o resto.
- Não leia além de
a.length - 1.
Agora você tenta
- Cada tarefa completa um método que o Harness chama com vários arrays.
- Reutilize os padrões acima: um total acumulado, um "melhor até agora", ou um contador.
- Use Check answer para compilar seu código com os testes fornecidos e visualizar os resultados. Mantenha as interfaces da classe e do método mostradas no modelo.
Scanning an array for the max
One pass keeps a running max, updating it when a bigger value appears.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete max(int[] a) so it returns the largest value in the array. You may assume the array has at least one value. It must work with negative numbers too.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete countEven(int[] a) so it returns how many values are even. A value is even when v % 2 == 0. An empty array returns 0.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete indexOf(int[] a, int target). Return the index of the primeiro tempo target appears. If it is not in the array, return -1.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Complete average(int[] a). Return the average of the values as a double. Divide by (double) a.length so you get a decimal, not integer division. You may assume the array is not empty.
Clique em Executar para ver a saída aqui.