Declaração do problema:
Você recebe uma matriz de inteiros arr de tamanho n.
Selecione uma subsequência de números inteiros e reorganize-os para formar uma sequência circular de modo que a diferença absoluta entre quaisquer dois números inteiros adjacentes (incluindo o último e o primeiro) seja no máximo 1.
Encontre o número máximo de inteiros que podem ser selecionados.
Observações:
Uma subsequência é formada pela exclusão de zero ou mais elementos sem alterar a ordem dos elementos restantes.
Os números inteiros selecionados podem ser reorganizados em qualquer ordem.
A sequência é circular — o último e o primeiro inteiros são considerados adjacentes.
Restrições:
1 <= n <= 2 × 10^5
0 <= arr[i] <= 10^9
Exemplos:
Input: arr = [4, 3, 5, 1, 2, 2, 1]
Output: 5
Explanation: maximum length subsequence is : [3, 1, 2, 2, 1], it can be rearranged to seq : [2, 1, 1, 2, 3] of length 5, note that the condition must be satisfied in circular also, means abs(seq[0] - seq[seq.length-1]) means abs(2-3) <= 0
Input: arr = [3, 7, 5, 1, 5]
Output: 2
Explanation: maximum length subsequence is : [5,5] of length 2
Input: arr = [2, 2, 3, 2, 1, 2, 2]
Output: 7
Explanation: maximum length subsequence is : [2,2,3,2,1,2,2] of length 7
Input: arr = [1,2,3,4,5]
Output = 2
Explanation: maximum length subsequence is : [1,2] or [2,3] or [3,4] or [4,5], so length is 2.
Observe que a subsequência também deve satisfazer a condição circular. Aqui está meu código:
import java.util.*;
class Main {
public static int solve(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int max = 0;
for (int num : freq.keySet()) {
int count = freq.get(num);
int countWithNext = freq.getOrDefault(num + 1, 0);
int countWithPrev = freq.getOrDefault(num - 1, 0);
max = Math.max(max, countWithPrev + count + countWithNext);
}
return max;
}
public static void main(String[] args) {
System.out.println(solve(new int[]{4,3,5,1,2,2,1})); // Expected: 5
System.out.println(solve(new int[]{3,7,5,1,5})); // Expected: 2
System.out.println(solve(new int[]{2,2,3,2,1,2,2})); // Expected: 7
System.out.println(solve(new int[]{1,2,3,4,5})); // Expected: 2
}
}
Sou capaz de encontrar as subsequências de comprimento máximo, mas não consigo encontrar como atender à condição circular, então, para o caso de teste [1,2,3,4,5], meu código está retornando 5 em vez de 2.
Além disso, a abordagem em si está falhando para a entrada [1,2,3,4,3,2], conforme comentado por John Bollinger
Qual é a abordagem correta para resolver isso com menos complexidade de tempo?
Observe bem a dica de @btilly nos comentários:
Isso é quase uma impressão digital que você pode igualar, mas antes de expandirmos para tal impressão digital, vamos primeiro considerar por que isso acontece.
Considere um membro s n de uma sequência circular contígua que não é nem seu valor mínimo nem seu valor máximo. Agora, suponha que percorremos o ciclo começando em s n . Antes de retornarmos a s n , percorreremos tanto o mínimo quanto o máximo da sequência e, como a sequência é organizada de forma contígua, entre eles devemos percorrer outro elemento cujo valor é o mesmo que s n . Portanto, todo membro que não é nem mínimo nem máximo na sequência deve ocorrer pelo menos duas vezes.
O mesmo não se aplica, contudo, ao mínimo ou ao máximo. Pode haver múltiplas ocorrências de um ou de ambos, mas ainda podemos formar um ciclo com apenas uma ocorrência de cada. No caso mais trivial, uma única ocorrência de um único número satisfaz os critérios, mas podemos ter uma única ocorrência de cada um dos valores mínimo e máximo com qualquer número total de elementos diferente de exatamente 3.
Agora, suponha que temos uma coleção de números contíguos, em qualquer ordem, tal que haja pelo menos duas ocorrências de cada um, exceto possivelmente o mínimo e o máximo entre eles. Podemos formar uma sequência circular a partir deles, primeiro ordenando-os em ordem crescente, depois pegando um de cada número que não é nem mínimo nem máximo e deslocando-os para o final, em ordem decrescente. Por exemplo,
Segue-se que, para que uma coleção de números seja adequada para formar o tipo de sequência circular que você deseja, é necessário e suficiente que (i) eles sejam contíguos e (ii) cada número que não seja o mínimo nem o máximo apareça pelo menos duas vezes.
AGORA você tem sua impressão digital. É possível encontrar a sequência máxima com essa impressão digital em O( n log n ) passos (pior caso), mas deixo você resolver os detalhes.
Seu código considera apenas as frequências dos "vizinhos" imediatos (em ordem de classificação) para determinar uma contagem. Isso gerará resultados incorretos quando a resposta correta envolver mais de 3 números distintos.
Contar frequências é uma boa abordagem, mas depois vá além dos vizinhos diretos do valor em questão. Também será útil procurar vizinhos apenas quando tiver certeza de que está em um limite inferior de um intervalo potencial — dessa forma, você só precisa varrer os valores em ordem crescente . Um valor é considerado "baixo" quando sua frequência é 1 ou não há ocorrência desse valor menos um.
Veja como o loop (depois de obter as frequências) pode ser feito para funcionar:
Supondo que as operações
geteputem um mapa hash tenham uma complexidade de tempo amortizada de O(1), esse algoritmo tem uma complexidade de tempo O(𝑛), onde 𝑛 é o tamanho da matriz de entrada.