Introdução
Bem-vindos ao nosso 14º artigo na série Preparação para Entrevistas, um guia para aqueles que estão se preparando para entrevistas técnicas. Nesta edição, estudaremos o seguinte problema: remover itens duplicados em um array ordenado. Este desafio não só é uma pergunta frequente em entrevistas técnicas, mas também serve como uma excelente oportunidade para refinarem suas habilidades em manipulação de arrays.
Neste artigo, forneceremos exemplos práticos em duas das linguagens de programação mais populares: Java e Python. Esses exemplos não apenas ilustrarão como resolver o problema de maneira eficaz, mas também ajudarão a entender as sutilezas e as diferenças entre essas duas linguagens ao lidar com arrays e operações de dados.
Antes de mergulharmos nos detalhes técnicos, vamos começar com uma compreensão clara do problema em questão.
Definição do Problema
O problema em questão trata de como eficientemente eliminar itens repetidos em um array ordenado.
Este desafio tem duas exigências chave: a eliminação dos itens duplicados deve ser feita “in-place” (isto é, sem o uso de estruturas de dados extras para armazenamento temporário), e após a eliminação das duplicatas, é necessário retornar o comprimento do novo array, que agora só possui elementos únicos.
Para exemplificar, considere um array ordenado como[1, 1, 2, 2, 3, 4, 4, 5]. Neste array, os números 1, 2 e 4 estão duplicados. O objetivo é transformar este array em [1, 2, 3, 4, 5, x, x, x], onde x representa um espaço vazio ou um valor irrelevante. O novo tamanho do array deve ser 5, pois este é o número de elementos únicos restantes após a remoção. E é esse novo tamanho do array que deve ser retornado neste problema
Soluções em Java e Python para Remoção de Itens Duplicados em Arrays Ordenados
Vamos agora implementar a solução do problema de remoção de itens duplicados em um array ordenado utilizando Java e Python.
public class Solucao {
public static int removeItemsDuplicados(int[] numeros) {
int tamanhoArray = numeros.length;
int esquerda = 0;
int direita = 1;
while (direita < numeros.length) {
if (numeros[esquerda] == numeros[direita]) {
tamanhoArray--;
} else {
numeros[esquerda + 1] = numeros[direita];
esquerda++;
}
direita++;
}
return tamanhoArray;
}
public static void main(String[] args) {
int[] numeros = {1, 1, 2, 2, 3, 4, 4, 5};
System.out.println(removeItemsDuplicados(numeros));
}
}Explicação do Código:
def remove_itens_duplicados(numeros):
esquerda = 0
for direita in range(1, len(numeros)):
if numeros[esquerda] != numeros[direita]:
esquerda += 1
numeros[esquerda] = numeros[direita]
return esquerda + 1
def main():
numeros = [1, 1, 2, 2, 3, 4, 4, 5]
novo_tamanho = remove_itens_duplicados(numeros)
print(novo_tamanho)
print(numeros[:novo_tamanho]) # Imprime a lista sem os duplicados
if __name__ == "__main__":
main()
Inicializações:
- tamanhoArray: Variável que guarda o tamanho original de um vetor.
- esquerda e direita: Dois ponteiros que irão comparar os elementos do vetor.
While:
- O laço vai percorrer até que o ponteiro da direita chegue ao fim do vetor.
Comparando e Excluindo Elementos Duplicados:
- Dentro do laço, se os elementos referenciados por esquerda e direita forem iguais (indicando uma duplicata), o tamanhoArray é decrementado e o ponteiro da direita incrementado.
- Se forem diferentes, os dois ponteiros direita e esquerda incrementados
Resultado:
- O método retorna tamanhoArray, que representa o número de elementos únicos no array após a remoção dos itens duplicados.
Análise de Complexidade
Complexidade de Tempo
O algoritmo itera sobre a lista de números uma vez, usando dois índices: esquerda e direita. A cada iteração, um dos índices avança. O índice direita percorre toda a lista, enquanto o índice esquerda avança condicionalmente. Portanto, a complexidade de tempo é linear em relação ao tamanho da lista n, sendo O(n).
Complexidade de Espaço
Em termos de espaço, o algoritmo não utiliza espaço adicional que cresce com o tamanho da entrada. Portanto, a complexidade de espaço é constante, independente do tamanho da entrada, sendo O(1).
Conclusão
Este algoritmo de remoção de itens duplicados em uma lista, ilustrou a importância de entender e manipular arrays de maneira eficiente, especialmente através da técnica de dois ponteiros. Apesar de sua aparente simplicidade, o algoritmo pode representar um desafio significativo para aqueles que não estão habituados com a manipulação de arrays. O desafio está na necessidade de manter o controle de múltiplos índices simultaneamente e compreender como eles interagem ao longo do array.
Esta abordagem de dois ponteiros é uma técnica interessante e proporciona uma maneira eficiente de resolver problemas que, à primeira vista, podem parecer complexos.
Se você achou este artigo útil e deseja aprofundar seu conhecimento em algoritmos, lembre-se de que ele faz parte de uma série explorando diferentes técnicas e conceitos em programação. Veja todos os artigos aqui.
👨💻🚀 Gostou do conteúdo? Comente abaixo suas experiências e dúvidas! Não esqueça de compartilhar com amigos que também estão se preparando para entrevistas. 👩💻🚀
Referências
Cracking the Coding Interview’ é um best-seller renomado e um favorito pessoal – um livro indispensável na preparação para entrevistas técnicas!
Designing Data-Intensive Applications: é uma referência para criar aplicações escaláveis, robustas e de alto desempenho!