Problema 704: Busca Binária

Dado um array ordenado em ordem crescente com n elementos inteiros nums e um valor-alvo target, implemente uma função para buscar o target no array. Retorne o índice se encontrado, caso contrário retorne -1.

Solução com Força Bruta

class Solution:
    def search(self, nums, target):
        contador = 0
        for pos in range(len(nums)):
            if nums[pos] == target:
                return pos
            contador += 1
        return -1 if contador == len(nums) else -1

Algoritmo de Busca Binária

A busca binária é eficiente para arrays ordenados, com complexidade O(log n). O processo envolve definir dois ponteiros, comparar o elemento central e reduzir o intervalo de busca pela metade a cada iteração.

Intervalo Fechado-Fechado

class Solution:
    def search(self, nums, target):
        inicio = 0
        fim = len(nums) - 1
        while inicio <= fim:
            meio = (inicio + fim) // 2
            if nums[meio] == target:
                return meio
            elif nums[meio] < target:
                inicio = meio + 1
            else:
                fim = meio - 1
        return -1

Intervalo Fechado-Aberto

class Solution:
    def search(self, nums, target):
        inicio = 0
        fim = len(nums)
        while inicio < fim:
            meio = (inicio + fim) // 2
            if nums[meio] == target:
                return meio
            elif nums[meio] < target:
                inicio = meio + 1
            else:
                fim = meio
        return -1

O método escolhido depende da definição dos limites, afetando as condições de parada e atualização dos ponteiros.

Problema 27: Remover Elemento

Considere um array nums e um valor val. Remova todas as ocorrências de val in-place e retorne o número de elementos restantes. A ordem dos elementos pode mudar.

Solução Inicial e Erros

class Solution:
    def removeElement(self, nums, val):
        contagem = 0
        for idx in range(len(nums)):
            pos = idx - contagem
            if nums[pos] == val:
                nums.pop(pos)
                contagem += 1
        return contagem, nums

Esta abordagem falha porque o LeetCode espera apenas o comprimento como retorno, não uma tupla. O array é modificado in-place, e a plataforma valida os primeiros k eelmentos após a chamada da função.

Método de Força Bruta

class Solution:
    def removeElement(self, nums, val):
        escrita = 0
        for leitura in range(len(nums)):
            if nums[leitura] != val:
                nums[escrita] = nums[leitura]
                escrita += 1
        return escrita

Aqui, escrita rastreia a posição para o próximo elemento válido, sobrescrevendo o array diretamente.

Técnica de Dois Ponteiros

Ponteiro Rápido e Lento

class Solution:
    def removeElement(self, nums, val):
        rapido = 0
        lento = 0
        tamanho = len(nums)
        while rapido < tamanho:
            if nums[rapido] != val:
                nums[lento] = nums[rapido]
                lento += 1
            rapido += 1
        return lento

O ponteiro rapido percorre o array, enquanto lento mantém a posição dos elementos válidos.

Pontieros Bidirecionais

class Solution:
    def removeElement(self, nums, val):
        n = len(nums)
        esquerda, direita = 0, n - 1
        while esquerda <= direita:
            while esquerda <= direita and nums[esquerda] != val:
                esquerda += 1
            while esquerda <= direita and nums[direita] == val:
                direita -= 1
            if esquerda < direita:
                nums[esquerda] = nums[direita]
                esquerda += 1
                direita -= 1
        return esquerda

Nesta variante, os ponteiros convergem do início e do fim, trocando elementos para eliminar valores indesejados, reduzindo operações em certos cenários.