Logo Passei Direto
Buscar
This is a demo task. Write a function: class Solution { public int solution(int[] A); } content_copy that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5. Given A = [1, 2, 3], the function should return 4. Given A = [−1, −3], the function should return 1. Write an efficient algorithm for the following assumptions: N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000..1,000,000].
User badge image
Cristine Moehlecke

mês passado

Respostas

User badge image

Ed Verified user icon

mês passado

Para resolver essa questão, precisamos criar uma função que encontre o menor inteiro positivo que não está presente no array fornecido. Vamos pensar passo a passo: 1. Filtrar os números negativos e zeros: Como estamos interessados apenas em números positivos, podemos ignorar todos os números que são menores ou iguais a zero. 2. Usar um conjunto (Set): Podemos usar um conjunto para armazenar os números positivos que estão presentes no array. Isso nos permitirá verificar rapidamente se um número está presente. 3. Iterar a partir do 1: Começamos a verificar a partir do número 1 e continuamos até encontrar o primeiro número que não está no conjunto. Aqui está uma implementação em Java da função solicitada: ```java import java.util.HashSet; class Solution { public int solution(int[] A) { HashSet set = new HashSet<>(); // Adiciona todos os números positivos ao conjunto for (int num : A) { if (num > 0) { set.add(num); } } // Verifica o menor inteiro positivo que não está no conjunto int smallestPositive = 1; while (set.contains(smallestPositive)) { smallestPositive++; } return smallestPositive; } } ``` ### Explicação do código: - Criamos um `HashSet` para armazenar os números positivos. - Iteramos pelo array `A`, adicionando apenas os números positivos ao conjunto. - Em seguida, começamos a partir do número 1 e verificamos se ele está no conjunto. Se estiver, incrementamos e verificamos o próximo número. - Quando encontramos um número que não está no conjunto, retornamos esse número. Essa abordagem é eficiente e atende às condições do problema.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Mais conteúdos dessa disciplina