Me perguntaram isso em uma entrevista pra uma startup no Texas, nunca tinha visto o problema. Demorei um pouco pra resolver, mas resolvi em O(n). Pediram pra implementar um LRU em O(1) também. Foi desafiador mas atingi o objetivo. Infelizmente n fui chamado pra vaga, acho que pela demora pra resolver o problema em primeira instância. Noto que a cultura dos norte americanos é mt forte pra leet code, bem diferente das empresas do Brasil
@@erikxw tudo certo cara? Quando falamos O(n), O(1), O(logn), entre outros, referimos a complexidade algoritmica, ou Big O Notation, que é utilizada para comparar a eficiência de algoritmos. É importante entender pelo menos o básico de estrutura de dados para conseguir determinar a complexidade de algum algoritmo. Alguns exemplos: O(1) - Chamado de constant time (tempo constante). É chamado assim pois a operação é sempre constante e não depende de N. Acessar um index em um array é feito em tempo constante O(1) por exemplo, pois já temos a referência em memória pronta para ser acessada. Operações simples como um println, atribuir valores a variáveis e etc também são feitas em tempo constante. O(n) - Chamado de Linear Time (tempo linear). Diferente do O(1), esse carinha depende de N. Iterar em uma lista é feito em Linear Time, pois iremos iterar em todos os itens da lista, podendo iterar N vezes até que a lista acabe. Outro caso de Linear Time pode ser acessar um valor em uma Linked List. Nesse caso da Linked List, para acharmos um valor específico começamos pelo primeiro valor na linked list, e através da referência ao próximo valor, vamos avançando na lista. Nesse cenário, no pior dos casos, o valor pode estar no final da lista, tornando o algoritmo em O(n). "- Há mas vc pode manter a referência do head e do tail da lista pra ficar mais rápido e etc", Entendo, mas essa explicação é mais simplificada pra cunho de entendimento. O(logn) - Chamado de Logarithmic Time (Tempo logaritmico). Esse cara utiliza um conceito bem comum na programação chamdo de Divide & Conquer (dividir e conquistar), pois a abordagem dele é literalmente o número de vezes que “n” pode ser dividido por 2 para encontrar o valor. Um Binary Search (busca binária), ou uma Balanced Sorted Binary Tree (arvore binária ordenada e balanceada) são exemplos de O(logn). Pode ser que, para achar um valor em uma busca binária vc demore log5 ou log7. Para ser mais geral, utiliza-se logn. Esses que citei são os mais básicos, comuns e utilizados. Você pode se aprofundar um pouco mais no assunto e com certeza vai se deparar com outras complexidades, como O(nlogn), O(n^2), O(n!), dentre outras.
Agora, falando sobre a LRU (Last Recently Used). Esse é um algoritmo de cache. Basicamente o que ele faz é armazenar um map de valores até uma certa capacidade. Quando existe a necessidade de adicionar um novo valor nesse cache e essa capacidade for atingida, você precisa remover do seu cache o valor que foi menos utilizado para que possa ser possível adicionar um novo valor. O problema parece simples, mas vc precisa pensar em como vai lidar com a ordem de acesso, a remoção e adição, o pop do valor mais utilizado. Com base na explicação de Big O que dei ali em cima, podemos pensar em alguns approaches pra atingir isso. Geralmente uttiliza-se um HashMap e um DoublyLinkedList. Ou, no meu caso, no Kotlin, tem um LinkedHashMap (mas lógico que vão pedir pra vc implementar ttudo na unha pra ver se vc entende hehe).
Portanto, pedir um LRU com Big O de O(1), basicamente estão pedindo para implementar esse algoritmo em tempo constante (que é o algoritmo mais rápido). Suas operações devem ser todas em O(1)
Um LRU (Last Recenly Used) é um algoritmo de cache. Basicamente vc precisa armamzenar um map de valores em um cache até uma determinada capacidade. Quando precisar armazenar um novo valor e essa capacidade tiver sido atingida, vc precisa remover do cache a chave que foi menos utilizada dentre as outras. Quando vc dá um get em um valor ele se torna o ultimo valor mais utilizado, por exemplo. E quando vc da um put nesse valor, a mesma coisa, mas aqui ele atualiza o valor atrelado a chave que está armazenada em cache. Parece um problema simples, vc aqui vc já precisa de preocupar com coisas como: - Como manter a ordem de acesso - Como remover, adicionar, dar update nos valores - O que fazer quando tentar dar um get em um valor que n está em cache - Quais esttruturas de dados vou uttilizar para que a Complexidade se mantenha em Big O (1)? Muito comum utilizarem HashMap e DoublyLinkedList para solucionar o problema.
Assim como a operação xor soma os dígitos na representação binária módulo 2 (isto é, soma e vê qual o resto do resultado na divisão por 2), pensei em definir uma outra operação que converte os números na base ternária e soma dígitos módulo 3.
A solução é engenhosa, mas seria bem mais fácil rodar 32 vezes _radix sort_ na base 2, uma para cada bit, e depois varrer a lista procurando o que aparece apenas uma vez. Claro que para isso ser considerado constante temos que contar com a limitação da quantidade de bits para cada número, o que poderia não ser verdade em Python ou com uso de algum BigInteger, mas isso já ocorre também no próprio xor, pois se fossem números com bilhões de bits isso de qualquer forma já teria que constar na fórmula do cálculo da complexidade algorítmica. O que nos leva a outro ponto: se precisamos contar com a limitação de bits para considerar como linear na quantidade de elementos, então por que não poderíamos fazer uso da própria limitação dessa quantidade de elementos para dizer que uma lista auxiliar também é limitada?! Dois pesos, duas medidas, de forma que não considero esse problema matematicamente preciso. Tem outra coisa: mesmo o radix sort teria 32 iterações, totalizando 32n operações, mas um simples sort de espaço adicional O(1) (por exemplo, heapsort) e tempo Θ(n log(n)) seria mais rápido, na prática, para n grandes até cerca de 2^30. Como a quantidade de elementos é *muito* menor que isso, um simples sort (até mesmo os prontos das linguagens de programação) passa no teste. Enfim, minha crítica ao problema é que precisa assumir algo (a limitação de bits) para ter solução de forma proposta, mas ao fazer isso abre espaço para fazer o mesmo do outro lado, considerando a limitação do número de elementos como um item necessário para afirmar que uma lista auxiliar ainda usa espaço constante.
Sugiro fazer o xor e subtrair ele duas vezes da soma do nums. O resultado será o valor único… assim não precisará de nenhuma outra variável de controle.
no leetcode fala pra resolver em tempo linear, O(n). Mas eu implementei em O(nlog(n)) com TreeMap e passou. porém apenas acima de 8.85% dos outros desenvolvedores Java, ou seja, pior do que 91.15% de todos os outros.
Não seria mais fácil só somar os bits modulo 3? Na pratica é a mesma coisa que tu tá fazendo, mas me parece mais simples de entender. Tipo, usa um array tamanho 32, um pra cada casa binária, soma todas as vezes que aquele bit aparece e no final faz modulo 3 das 32 variaveis? usa alguns bytes a mais, mas na minha cabeça parece um pouco mais simples de explicar. 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 somando: 3 1 4 0 modulo 3: 0 1 1 0
Se fossemos querer isso sabendo que teríamos no max N números repetidos, então faríamos a mesa coisa mas modulo N no final? Se tiver correto meu entendimento, esse método é ótimo já que é escalável sem precisar adicionar mais linhas de código
@@blext816 sim, daria pra deixar mais amplo ainda. Se fosse encontrar um numero que se repete N vezes, enquanto os outros se repetem M vezes (dado que M != N, M != 1), tu faria modulo M, não importando qual o N, só precisaria transformar os valores não-0 em 1 E os casos M == N e M == 1 são triviais
Cara top de mais, mas se tiver uma sequencia de números aleatório, digamos todos entre 0 e 9, como determinar quais números não se repetem, e se algums números aparecem 2 e outros 3 vezes Pelo que entendi o primeiro algoritmo serve para um uso geral e os demais servem para um uso especifico, mas ainda sim é válido, muito obrigado pelo vídeo você é 10
Eu não sou programador, não sei programar e nunca tentei, eu assisti seu vídeo só pq me prendeu no ínicio, queria te dizer que sua didática foi tão incrível que por mais que eu não tenha entendido mt bem a programação, entendi a lógica, isso foi incrível!!!
Exatamente meu amigo! isso é Matemática (Lógica!), códigos qualquer imprestável escreve! Desenvolver um algoritmo eficiente (Possível Solução no mínimo Boa) é que é difícil!
Minha solução seria ordenar o vetor, depois andar por ele verificando o quanto se repete, e se repetir 2x pularia +1 casa desconsiderando a terceira vez que o numero repete
o fato de ser linerar sinifica q vc deve percorrer o array apenas uma unica vez. e memoria constante é como foi explicado no video. e a soluçao é realmente o unico jeito de ser linear e memoria constante. q no caso ele usou apenas 2 variaveis. ou seja o uso de memoria escala com o problema em si mas nao com o tamanho do problema. se o problema fosse de forma q os numeros se repetem 4 vezes ao inves de 3, teriamos q adicionar mais uma variavel.
@@ykyjohn não, ser linear não significa que você precisa percorrer o array apenas uma vez. Apenas que a quantidade de tempo de vezes que você percorre o array não pode escalar com o tamanho do array O(1000x) = O(x)
Primeiro de sort em num. crie um loop onde ele caminha nos elementos da lista, e faça uma leitura do próximo item da lista. Caso o próximo seja igual, então coloque uma condição que enquanto o número for X é continue. Se o ciclo recomeçar e o próximo não for igual, ou chegar ao fim sem duplicatas, então ele é único.
de fato funciona ahaha embora nas constraint do problema menciona que a solucao precisa ser em O(N). Como a sua solução requer um "sort" estamos falando de ao menos O(n log n) (para algoritmos que usam comparação como quick, merge) vale ver os que usam a abordagem de contagem mas para isso creio que seria necessario outro array para a "contagem".
Em linguagem Python, a utilização de in pode ser bastante útil para esses problemas. Eu não sei se faz parte da regra eliminar a lista principal, ou alterar a numeração dos índices, mas se isso for permitido, uma ideia seria while nums: vari = nums.pop(0) if vari in nums: while vari in nums: nums.remove(vari) else: break Se a memória da lista precisar ficar intacta, um algoritmo que retorna o número de ocorrências de verificação linear poderia percorrer um a um: for i in nums: if nums.count(i) == 3: continue else: return i Se a lista poder ser semi alterada, você pode fazer uma brincadeira de ir jogando o item da frente para trás, mantendo-os na mesma lista, parando apenas no item único: while True: vari = nums.pop(0) if vari in nums: nums.append(vari) else: nums.append(vari) return nums[-1] ETC
Todas essas soluções tem complexidade de tempo quadrática e não linear como o exercício pede. Na sua primeira solução: O método nums.remove percorre o vetor inteiro para encontrar o número a ser removido, como ele faz isso para cada valor do vetor então é O(n*n) = O(n^2) Na sua segunda solução: método nums.count literalmente percorre o vetor inteiro contando quantas vezes o número aparece, logo se ele percorre o vetor 1 vez para cada número no vetor é O(n*n) = O(n^2) Na terceira você usa "if vari in nums" para determinar se isso é verdadeiro ou falso ele percorre nums inteiro procurando a variável, logo se ele percorre o vetor uma vez para cada elemento então é O(n*n) = O(n^2) Esse é um probleminha do python, usando as funções que ele tem implementado pode ficar difícil de perceber a eficiência do próprio código, por não saber como foi feita a implementação dessas funções.
@@Renan_PS-zt8lm Acredito que estamos tendo um erro de contextualização. Por definição, "Linear Complexity" aumenta conforme a quantidade do input (tamanho do iterável lista[int]), a cada elemento. Em outras palavras, se um elemento tem 1 tempo para ser resolvido, se colocar 2 elementos o tempo de execução deve ser 2 tempos. Logo, se para analisar 1 item ele leva 0.05 segundos, com 2 itens ele deve levar 0.10 segundos, e assim sucessivamente Dentro do conceito de n², se eu aumentar 1 item, esse tempo multiplica. Ou seja, se um programa leva 0.05 segundos, com 2 itens ele leva 0.25 segundos, por causa dos protocolos de percorrimento. Nos percorrimentos dos algoritmos apresentados, a execução do programa não se multiplica de n² por cada input a mais, são execuções de percorrimento simples. Em outras palavras, se demora 0.10 segundos para encontrar o elemento único em uma lista com 10 elementos, é de complexidade linear que ele demore 1 segundo em uma lista com 100 elementos. Um erro dos exemplos do qual eu entenderia a crítica seria "Mas no programa não pode alocar memória para responder, ou seja, criar variáveis", eu entenderia, e responderia algo mais simplório ainda: while len(nums.count(nums[0])) == 3: nums.append(nums.pop(0)) return nums[0] E assim nem variável seria utilizada. Esse tipo de problema não é sobre agilidade de processamento, mas sim sobre algoritmo que não use muito memória, mesmo que demorado. Não necessariamente um algoritmo de Complexidade Linear é ágil, porém, mais ágil que outros.
@@TheRageOm O exercício específica que a complexidade de memória deve der constante e a complexidade de tempo tem que ser linear. O nums.count não descobre quantas vezes um elemento aparece no vetor magicamente, na implementação da função ele percorre o vetor inteiro e conta quantas vezes aparece. Ou seja, se você chama um nums.count (O(n)) para cada elemento do seu vetor (O(n)) a complexidade de tempo do algoritmo fica O(n^2). Quando falamos da complexidade de memória, criar variáveis ou não não impacta na complexidade assintótica, a não ser que o número de variáveis cresça com o tamanho do vetor. Assintótica significa que constantes multiplicativas são desconsideradas, logo O(4627193) = O(1).
@@Renan_PS-zt8lm O problema é que você está interpretando que o script está lendo a lista. Ler a lista faz parte da subrotina. O conceito de O(n²) não é para scripts, mas sim para as consequências de adicionar mais ou menos elementos ao iterável. Desta forma, ao adicionar 1 elemento, ela não aumenta o tempo linearmente, mas de forma exponencial. Isso ocorre com base no código, mas o conceito se aplica aos tamanhos dos iteráveis. Vou dar um exemplo: - uma str com len == 4 - cada caractere vai de a até z - quantas formações aleatórias são criadas? Caso eu aumente essa str para 5, aumenta consideravelmente, se for 6, ainda mais, etc Isso não ocorre nos exemplos apresentados.
@@TheRageOm Nos seus exemplos, se a lista tiver 4 elementos vai demorar 16t, sendo t um intervalo de tempo constante arbitrário, agora se tiver 5 elementos vai 25t. Crescimento quadrático.
dar sorted na lista e fazer um for que pula de 3 em 3, e parar quando achar um item da lista q o proximo dele não seja igual a ele seria uma maneira eficiente?
Radix sort pode ter tempo linear em casos que a quantidade de dígitos não crescem significativamente com o tamanho da conjunto, que é o caso aqui. Realmente pode ser uma boa! Foda é lembrar como implementar de cabeça kkkkkkkk
o problema tem uma restrição onde todo numero na array de input aparece exatamente 3 vezes, exceto o número que tentamos encontrar, que aparece apenas uma vez, pra mim é mais facil apenas usar um hashmap que mantém a quantidade de vezes encontramos um número e deletar do hashmap caso foi encontrado mais de 2 vezes, assim o unico numero que sobra no hashmap é o numero que aparece apenas 1 vez, acessar um numero no hashmap sempre será O(1) e dessa forma vc sempre corre pelo array 1 vez, ou seja, no final dá O(n) da mesma forma com um código imensamente mais compreensível
Não vou resolver nem ver o vídeo mas tragoa solução. Ao invés de procurar o unico elemento é só procurar os elementos repetidos pois é muito mais fácil. Depois de encontrar todos é só eliminar e ficar com o restante. se for apenas 1 numero único, você ficará com o único, se forem algums vc ficará com algums.
Eu resolvi de maneira pais pragmatica... conta os bits numa lista. Faz mod 3 na lista depois reconstroi o numero. A complexidade e identica ja que o tamanho do inteiro e constante, porem nao tem magia nenhuma. O lado bom da solucao por contagem de bits e que da pra fazer pra qualquer numero de repeticoes sem nenhum problema, sei la, 7 repeticoes.
Acho que é mais fácil de entender se fazer twos ^= num & ones; ones ^= num & ~twos; Trocando a ordem voce pode verificar o ones anterior para utilizar no twos
Fiz assim, mas n li direito as regras rs, mas é bem legal o desafio const number2 = array.find(i => { if (array.filter(j => j === i).length === 1) return i }) ou assim const number = array.find(i => { if (array.filter(j => j === i).length !== 3) return i })
Não assisti o vídeo (ainda) e resolvi o problema usando o thumbnail com javascript. Não sei as especificações e provavelmente existem formas melhores de se fazer, mas levei uns 3 minutos pra fazer: let a = [2,7,7,2,3,2,7] let b = []; a.forEach(item => { if(a.filter(i => i === item).length === 1) b.push(item) }); enfim, com certeza da pra melhorar isso, mas é funcional.
cara gostei bastante desse canal, pois diferentemente dos outros canais que tem hoje em dia que só falam coisas basicas e vendem mentiras (tipo com 6 meses vc conseguir trampo pra ganhar 10k) esse canal aborta leet code e praticas de software que me agregaram, continue assim
cara, é so fazer manipulação de arquivo ue, tu pega um numero e coloca no arquivo e ordena por la ou faz o count la. ele explicitou em memoria e não memoria secundaria/armazem externo
Se vc usar essa forma, vc com certeza adicionará no mínimo Time Complexity pra ler ou ordenar o arquivo. E Space Complexity não depende de onde seus dados estão, o fato de vc usar memória adicional dependente do tamanho do array já viola a complexidade de espaço. A resolução mostrada no vídeo cumpre ambas as soluções de complexidade de tempo e espaço.
Esses problemas geralmente são para serem resolvidos com a menor complexidade possível, mas a solução em si é facil, só agrupar os valores e pegar o com Count/Length == 1 kkkkkkkk
Agrupar os valores faz a complexidade de espaço não ser mais O(1) pois o tamanho desses valores agrupados dependerá do tamanho do array fazendo sua solução ter complexidade espacial O(N) e não O(1) que é um dos requisitos do problema.
Em Js é tao simples: const list = [2,1,1,2,2,3,3,4,4,5] let one = false; for (const num of list){ const achou = list.filter((p)=> p===num).length; if(achou === 1)one=num; } // Log to console console.log('One:',one)
Pensei nisso, problema de ordenar é que a memória vai ser alterada dinamicamente (vai ser alocado na memória uma nova variável com o mesmo tamanho do input), exceto que fabrique teu próprio código para ordenar manipulando/destruindo a variável de entrada
Eu esqueci de mencionar no vídeo, mas isso quebra outra premissa do problema. Precisa ter linear runtime complexity, ou seja, rodar em O(n). ordenar é n log n
como brincadeira isso é mto legal mesmo. o foda é usarem essas paradas em entrevistas, ou tipo o caso do primeiro comentário que perdeu o emprego pq não fica fazendo essas porras. dai o cara sabe leetcode e não sabe estruturar um código legível, ou debugar algo complexo, nem entro no mérito de quais arquiteturas de software usar para cada problema. tipo, tu só seleciona gente com tempo e paciência para ficar brincando, que não necessariamente vai adicionar numa empresa.
Isso nunca será um problema pra big techs. Eles tem dinheiro de sobra pra queimar treinando seus funcionários e tão pouco se importando se você tem habilidades em escrita de código legível e habilidades pra debugar códigos complexos. Eles não precisam disso, eles tem a comunidade open source pra debugar e melhorar o código se for necessário. A regra é que código é descartável, e os projetos que eles desejam manter por muito tempo vira open source, e toda a comunidade que usa código faz esse trampo que você falou. "tu só seleciona gente com tempo e paciência para ficar brincando". É esses caras que eles precisam. Se alguém surge com uma ideia que vai de algum modo contribuir com o modelo de negócio ou estratégia do conglomerado, é desses caras que tiveram tempo pra ficar brincando com peculiaridades de complexidades e firulas de algoritmos que eles precisam pra fazer o bagulho funcionar. De acordo com o livro do Google, a primeira versão do rankeador era um lixo de código. Foi reescrita várias vezes (do zero) durante os primeiros anos do google. Mas ainda assim o valor que esses ranqueador entregava já era anos luz a frente dos concorrentes.
`input = [2,2,3,2] def single_number(arr): if len(arr) == 0: return 0 else: if len(arr) == 1: return arr[0] else: return arr[0] if arr[0] not in arr[1:] else single_number(arr[1:]) print(single_number(input))`quando resolvi sem ver o vídeo fiz assim e nem percebi que era O(1)
No pior caso, ele vai executar essa operação IN uma vez pra cada elemento do array, ou seja, no final a complexidade não é linear e sim quadrática. E acredito que o uso de slice como arr[1:] também crie uma lista em memória pra fazer a comparação, então acho que também acaba que não fica O(1) a complexidade de espaço
@@derkonig7820 Em relação a espaço, eu acho que a lista que a função slice cria só é usada na operação do IN e depois é excluida então creio que seja O(n) (me corrige se estiver errado kkkk), mas em relação a complexidade de tempo é n^2 sim no pior caso
Esse problema é bem simples, é só rodar um for na lista e criar outra lista com as frequências de cada elemento na lista principal, depois você saberá quais elementos tem na lista e quantas vezes eles se repetiram
isso funcionaria? class Solution: def singleNumber(self, nums: List[int]) -> int: for j in range(len(nums)): x = 0 for i in range(len(nums)): if nums[j] == nums[(-i-1)] and ((-i-1)+len(nums)) != j: x = 1 if x == 0: y = nums[j] return y
Acredito que não, pois nesse algoritmo a verificação se daria por matriz de ij, sendo que é dito nas restrições que todas as réplicas de int aparecem três vezes, exceto um (que aparece uma única vez). Ao longo da análise, y armazenaria apenas o que não apareceu 2 vezes na matriz. Mas, e se x == 1? Logo, o código nunca resolveria o valor de y, dando erro de execução. Esse erro, apesar de parecer impossível, deve ser evitado, pois existe uma probabilidade dele acontecer (lista int com apenas um valor). Outra restrição é que a análise deve ser feita em tempo O(n), ou seja, o tempo por item deve crescer de forma linear com o tamanho de itens. Nessa execução, seria algo mais parecido O(n²), por se tratar de análise em matriz, deixando o tempo o quadrado de tempo a ser analisado Então acredito que sim, pode funcionar, mas para o problema é inviável segundo os requerimentos.
Achei a parte do FOR com IF meio complicada. Preferi assim: nums = [0,1,0,1,0,1,99] nums2 = [2,2,3,2] x = [n for n in nums if nums.count(n) ==1] y = [n for n in nums2 if nums2.count(n) ==1] print(*x) print(*y)
Entao, mas esse é ponto desse video, ele sabe que essa é a solucao mais facil e rapida de se pensar, mas o problema quer que voce resolve em O(1) ou seja ele nao quer que voce percorra o array mais de uma vez, que é o que voce esta fazendo em .count()
@@MrZ1kaO problema quer O(1) em espaço, então o problema não é percorrer o array mais de uma vez, o problema é ter um array cujo tamanho depende da entrada
Caraca, fritei o cerebelo mas ACHO que entendi. Eu estudo Python a algum tempo, mas as operações que geralmente uso são "not", "and" e "or". É a primeira vez que vejo esses operadores |, ^, ~ sendo usados em um programa. Qual o nome desse assunto pra eu poder estudar?
Impossivel??? O que é isso então? let toCheck = [1, 1, 3, 2, 3, 1, 3, 1, 4, 2]; for (let i = 0; i < toCheck.length; i++) { let qtd = 1; for (let j = 0; j < toCheck.length; j++) { if (j === i) continue; if (toCheck[i] === toCheck[j]) { qtd++; break; } } if (qtd === 1) { console.log(toCheck[i]); //Aqui é o return, inclusive pode tirar o break break; } }
Na descrição do problema diz que precisa ser em tempo linear. Ou seja, O(n). Eu esqueci de deixar isso mais claro no meu vídeo. Esse é o motivo que não da pra resolver com .sort() por exemplo também
Eu sei que não. Mas for i.... for j são duas iterações sobre o array. Isso faz com que ela seja O(n2) e não O(n). O motivo que não da pra usar essa é o mesmo motivo que não dá pra usar sort. A complexidade temporal precisa ser O(n), não da pra fazer loop dentro de loop@@ZantsuRocks
cara eu achei na verdade esse exercício nível fácil pra ser sincero com um simples sort e um loop for voce resolve. PS: eu sou programador a 9 meses e resolvi em menos de 20 minutos dessa forma. Runtime:55ms Beats 67% | JS Users Memory:49.77MB Beats 71% | JS Users
var singleNumber = function(nums) { let n = nums.sort((a, b) => a-b); var saw=n[0]; for(let i = 1; i < n.length; i++){ if(n[i+1] == undefined){ if(n[i] != saw && n[i] != n[i-1])saw=n[i] }else { if(n[i] != saw && n[i+1] != n[i] && n[i] != n[i-1])saw=n[i] } } return saw; }; Lembrando que essa estrutura foi feita por um iniciante e mantem a estrutura O(1) e armazena apenas um valor independente do tamanho de nums
Quebra premissa do problema, tem que resolver em complexidade temporal linear, sort é O n log n. Eu sei que passa no leetcode, mas numa entrevista por exemplo não ia passar
@@GutoGalego bom sábado pra você. eu acordei tem alguns minutos e decidi refazer o código dessa vez levou menos de 10 minutos poderia confirmar pra mim se agora está em O(n)? var singleNumber = function(nums) { let n = nums.sort((a, b) => a-b); var saw=n[0]; var count=1; for(let i = 1; i < n.length; i++){ if(n[i] == saw){ count++; i++; }else if(n[i] != saw){ if(count > 1){ count=1; saw = n[i]; } } } return saw; }; eu percorro uma vez e apenas verifico se o numero já foi visto caso sim. eu pulo um a mais e continuo verificando. Se puder me ajudar eu ficaria grato no leetcode passou tambem
Bem, li o titulo, me senti meio intrigado, entrei no vs code e criei um script em python...: lista = [2, 7, 7, 2, 3, 2, 7] counter = {} for i in lista: if i not in counter: counter[i] = 1 elif i in counter: counter[i] += 1 print(counter) Deu certo. Talvez em outra linguagem, tipo C, talvez nao conseguiria implementar desse jeito. Mas enfim, sou um mero aprendiz, hehe.....
Nessa solução o seu counter faz o seu algoritmo ter complexidade espacial O(n) em vez de O(1). Vc precisa de uma solução que não aloque memória que dependa do tamanho do array inicial.
Interessante a solução, porém acredito que a primeira abordagem estava correta. O espaço não vai ser O(n) pois ele não cresce de acordo com a quantidade de elementos mas sim com os valores que o array pode conter, que de acordo com a questão varia entre -2³¹ e 2³¹-1. Dessa forma, independente da quantidade de elementos, o dicionário terá um tamanho constante pois ele irá armazenar valores e não elementos do array.
www.tjsc.jus.br/web/servidor/dicas-de-portugues/-/asset_publisher/0rjJEBzj2Oes/content/como-concordar-frases-com-percentual-ou-porcentual- De nada amigão, recebeu aula de software, de português e aprendeu a não ser pedante, principalmente quando não sabe do que ta falando.
@@felipe.raposo eu nem entendi se é meme ou não o que esse cara ta falando KKKKKKK. Só sei que o que fez o comentário original é o tipo de pessoa mais insuportável da internet. O desnecessariamente pedante. No caso agora ele ficou bem quietinho e sumiu pq ele percebeu que ele tava errado e passou altas vergonha.
Só registrando minha solução de iniciante coda fofo no início do vídeo: criaria um novo array e uma função em loop para verificar o próximo item do array principal, se for diferente dos itens anteriores adicionaria o valor ao novo array, se não, sendo igual a algum anterior excluiria do novo array. Acho que usaria find pra vasculhar o array, e um for loop pra função, mas confesso que nem sei certo de cabeça como implementaria pra funcionar
Наука
6:49 isso é um 6 em decimal, 3 decimal em binário seria 11.
também notei isso e fiquei me perguntado se eu tava louco
mesmo assim, conteúdo fantástico e bem apresentado
Fantástico, Augusto! Problema lindo! Solução muito elegante! Obrigado por esse vídeo.
Me perguntaram isso em uma entrevista pra uma startup no Texas, nunca tinha visto o problema. Demorei um pouco pra resolver, mas resolvi em O(n). Pediram pra implementar um LRU em O(1) também. Foi desafiador mas atingi o objetivo.
Infelizmente n fui chamado pra vaga, acho que pela demora pra resolver o problema em primeira instância. Noto que a cultura dos norte americanos é mt forte pra leet code, bem diferente das empresas do Brasil
Olá, o que significa O(n) e LRU em O(1), pode me explicar?
@@erikxw tudo certo cara? Quando falamos O(n), O(1), O(logn), entre outros, referimos a complexidade algoritmica, ou Big O Notation, que é utilizada para comparar a eficiência de algoritmos. É importante entender pelo menos o básico de estrutura de dados para conseguir determinar a complexidade de algum algoritmo.
Alguns exemplos:
O(1) - Chamado de constant time (tempo constante). É chamado assim pois a operação é sempre constante e não depende de N. Acessar um index em um array é feito em tempo constante O(1) por exemplo, pois já temos a referência em memória pronta para ser acessada. Operações simples como um println, atribuir valores a variáveis e etc também são feitas em tempo constante.
O(n) - Chamado de Linear Time (tempo linear). Diferente do O(1), esse carinha depende de N. Iterar em uma lista é feito em Linear Time, pois iremos iterar em todos os itens da lista, podendo iterar N vezes até que a lista acabe. Outro caso de Linear Time pode ser acessar um valor em uma Linked List. Nesse caso da Linked List, para acharmos um valor específico começamos pelo primeiro valor na linked list, e através da referência ao próximo valor, vamos avançando na lista. Nesse cenário, no pior dos casos, o valor pode estar no final da lista, tornando o algoritmo em O(n). "- Há mas vc pode manter a referência do head e do tail da lista pra ficar mais rápido e etc", Entendo, mas essa explicação é mais simplificada pra cunho de entendimento.
O(logn) - Chamado de Logarithmic Time (Tempo logaritmico). Esse cara utiliza um conceito bem comum na programação chamdo de Divide & Conquer (dividir e conquistar), pois a abordagem dele é literalmente o número de vezes que “n” pode ser dividido por 2 para encontrar o valor. Um Binary Search (busca binária), ou uma Balanced Sorted Binary Tree (arvore binária ordenada e balanceada) são exemplos de O(logn). Pode ser que, para achar um valor em uma busca binária vc demore log5 ou log7. Para ser mais geral, utiliza-se logn.
Esses que citei são os mais básicos, comuns e utilizados. Você pode se aprofundar um pouco mais no assunto e com certeza vai se deparar com outras complexidades, como O(nlogn), O(n^2), O(n!), dentre outras.
Agora, falando sobre a LRU (Last Recently Used). Esse é um algoritmo de cache. Basicamente o que ele faz é armazenar um map de valores até uma certa capacidade. Quando existe a necessidade de adicionar um novo valor nesse cache e essa capacidade for atingida, você precisa remover do seu cache o valor que foi menos utilizado para que possa ser possível adicionar um novo valor.
O problema parece simples, mas vc precisa pensar em como vai lidar com a ordem de acesso, a remoção e adição, o pop do valor mais utilizado.
Com base na explicação de Big O que dei ali em cima, podemos pensar em alguns approaches pra atingir isso. Geralmente uttiliza-se um HashMap e um DoublyLinkedList. Ou, no meu caso, no Kotlin, tem um LinkedHashMap (mas lógico que vão pedir pra vc implementar ttudo na unha pra ver se vc entende hehe).
Portanto, pedir um LRU com Big O de O(1), basicamente estão pedindo para implementar esse algoritmo em tempo constante (que é o algoritmo mais rápido). Suas operações devem ser todas em O(1)
Um LRU (Last Recenly Used) é um algoritmo de cache. Basicamente vc precisa armamzenar um map de valores em um cache até uma determinada capacidade. Quando precisar armazenar um novo valor e essa capacidade tiver sido atingida, vc precisa remover do cache a chave que foi menos utilizada dentre as outras.
Quando vc dá um get em um valor ele se torna o ultimo valor mais utilizado, por exemplo. E quando vc da um put nesse valor, a mesma coisa, mas aqui ele atualiza o valor atrelado a chave que está armazenada em cache.
Parece um problema simples, vc aqui vc já precisa de preocupar com coisas como:
- Como manter a ordem de acesso
- Como remover, adicionar, dar update nos valores
- O que fazer quando tentar dar um get em um valor que n está em cache
- Quais esttruturas de dados vou uttilizar para que a Complexidade se mantenha em Big O (1)?
Muito comum utilizarem HashMap e DoublyLinkedList para solucionar o problema.
parabéns! conteúdo incrível, abriu minha mente de como encarar alguns problemas e possíveis soluções
Incrível esse aula, muito obrigado!
Seus vídeos são demais mano!
Assim como a operação xor soma os dígitos na representação binária módulo 2 (isto é, soma e vê qual o resto do resultado na divisão por 2), pensei em definir uma outra operação que converte os números na base ternária e soma dígitos módulo 3.
Faz um radix sort, testa se 2 em sequencia são iguais, se sim soma 3 pro index, se não ou se for o último retorna ele
A solução é engenhosa, mas seria bem mais fácil rodar 32 vezes _radix sort_ na base 2, uma para cada bit, e depois varrer a lista procurando o que aparece apenas uma vez. Claro que para isso ser considerado constante temos que contar com a limitação da quantidade de bits para cada número, o que poderia não ser verdade em Python ou com uso de algum BigInteger, mas isso já ocorre também no próprio xor, pois se fossem números com bilhões de bits isso de qualquer forma já teria que constar na fórmula do cálculo da complexidade algorítmica. O que nos leva a outro ponto: se precisamos contar com a limitação de bits para considerar como linear na quantidade de elementos, então por que não poderíamos fazer uso da própria limitação dessa quantidade de elementos para dizer que uma lista auxiliar também é limitada?! Dois pesos, duas medidas, de forma que não considero esse problema matematicamente preciso. Tem outra coisa: mesmo o radix sort teria 32 iterações, totalizando 32n operações, mas um simples sort de espaço adicional O(1) (por exemplo, heapsort) e tempo Θ(n log(n)) seria mais rápido, na prática, para n grandes até cerca de 2^30. Como a quantidade de elementos é *muito* menor que isso, um simples sort (até mesmo os prontos das linguagens de programação) passa no teste. Enfim, minha crítica ao problema é que precisa assumir algo (a limitação de bits) para ter solução de forma proposta, mas ao fazer isso abre espaço para fazer o mesmo do outro lado, considerando a limitação do número de elementos como um item necessário para afirmar que uma lista auxiliar ainda usa espaço constante.
Se dá pra fazer and not, daria pra fazer uma tabela verdade de 3 elementos também concatenado ?
Sugiro fazer o xor e subtrair ele duas vezes da soma do nums. O resultado será o valor único… assim não precisará de nenhuma outra variável de controle.
video sensacional. Quando você postou no twitter fiquei pensando no problema por vários dias.
é um problema divertido, dps de fazer a matéria de sistemas digitais tudo fica bem claro
Tive que assistir 2 vezes pra entender. Fritou muito a cabeça kkkkkkk
Gosto muito do seu Canal.
no leetcode fala pra resolver em tempo linear, O(n). Mas eu implementei em O(nlog(n)) com TreeMap e passou. porém apenas acima de 8.85% dos outros desenvolvedores Java, ou seja, pior do que 91.15% de todos os outros.
Eu considero esse desafio médio, parabéns pelo vídeo.
isso não seria meio que fazer soma e subtração sequencialmente até terminar os valores do array?
Não seria mais fácil só somar os bits modulo 3? Na pratica é a mesma coisa que tu tá fazendo, mas me parece mais simples de entender. Tipo, usa um array tamanho 32, um pra cada casa binária, soma todas as vezes que aquele bit aparece e no final faz modulo 3 das 32 variaveis? usa alguns bytes a mais, mas na minha cabeça parece um pouco mais simples de explicar.
1 0 1 0
1 0 1 0
1 0 1 0
0 1 1 0
somando:
3 1 4 0
modulo 3:
0 1 1 0
Se fossemos querer isso sabendo que teríamos no max N números repetidos, então faríamos a mesa coisa mas modulo N no final? Se tiver correto meu entendimento, esse método é ótimo já que é escalável sem precisar adicionar mais linhas de código
@@blext816 sim, daria pra deixar mais amplo ainda. Se fosse encontrar um numero que se repete N vezes, enquanto os outros se repetem M vezes (dado que M != N, M != 1), tu faria modulo M, não importando qual o N, só precisaria transformar os valores não-0 em 1
E os casos M == N e M == 1 são triviais
Parabéns, única resposta diferente do vídeo que eu li e parece fazer sentido.
4:35 Esse reduce e esse xor aí não vão dar undefined??
Rapaz realmente praticamente impossível pensar nessa solução sem ter visto algo parecido antes kkk,
Cara top de mais, mas se tiver uma sequencia de números aleatório, digamos todos entre 0 e 9, como determinar quais números não se repetem, e se algums números aparecem 2 e outros 3 vezes
Pelo que entendi o primeiro algoritmo serve para um uso geral e os demais servem para um uso especifico, mas ainda sim é válido, muito obrigado pelo vídeo você é 10
Eu não sou programador, não sei programar e nunca tentei, eu assisti seu vídeo só pq me prendeu no ínicio, queria te dizer que sua didática foi tão incrível que por mais que eu não tenha entendido mt bem a programação, entendi a lógica, isso foi incrível!!!
Exatamente meu amigo! isso é Matemática (Lógica!), códigos qualquer imprestável escreve! Desenvolver um algoritmo eficiente (Possível Solução no mínimo Boa) é que é difícil!
Caraca, peguei aqui pra resolver e gastei 1 hora, mas consegui fazer sem pesquisar, só com meu conhecimento em Java. Top!
Minha solução seria ordenar o vetor, depois andar por ele verificando o quanto se repete, e se repetir 2x pularia +1 casa desconsiderando a terceira vez que o numero repete
os algoritmos de sort mais eficientes são n log n, exceto pelo bucket sort
@@sLokJoNas então essa seria minha primeira solução, não a ideal
Mas a questão fala que tem que ser linear
o fato de ser linerar sinifica q vc deve percorrer o array apenas uma unica vez. e memoria constante é como foi explicado no video. e a soluçao é realmente o unico jeito de ser linear e memoria constante. q no caso ele usou apenas 2 variaveis. ou seja o uso de memoria escala com o problema em si mas nao com o tamanho do problema. se o problema fosse de forma q os numeros se repetem 4 vezes ao inves de 3, teriamos q adicionar mais uma variavel.
@@ykyjohn não, ser linear não significa que você precisa percorrer o array apenas uma vez. Apenas que a quantidade de tempo de vezes que você percorre o array não pode escalar com o tamanho do array
O(1000x) = O(x)
Alguém pode passar o link do vídeo onde ele resolve a parte 1 do problema? Fiquei com algumas dúvidas.
Adoro seus vídeos, porém, sempre o seu áudio está MUITO baixo. :(
para mim está tranquilo o audio dele
Tá surdo merda
Pra mim tbm fica bem baixo
Aqui está tranquilo
Primeiro de sort em num.
crie um loop onde ele caminha nos elementos da lista, e faça uma leitura do próximo item da lista.
Caso o próximo seja igual, então coloque uma condição que enquanto o número for X é continue.
Se o ciclo recomeçar e o próximo não for igual, ou chegar ao fim sem duplicatas, então ele é único.
de fato funciona ahaha embora nas constraint do problema menciona que a solucao precisa ser em O(N). Como a sua solução requer um "sort" estamos falando de ao menos O(n log n) (para algoritmos que usam comparação como quick, merge) vale ver os que usam a abordagem de contagem mas para isso creio que seria necessario outro array para a "contagem".
@@augusto1997 radix sort é linear.
@@thiagovieira8569 yep. Embora ele não é O(1) em espaço. Ou seja ele precisa de memoria extra para auxiliar na ordenação.
@@augusto1997 mas essa memória extra cresce com mais dados de entrada? por que se não, não faz diferença alguma assintoticamente!
@@thomasthemazzerrunner3615 sim essa memória extra cresce com o o input, ou seja, nenhuma solução com sort resolve o problema
Esta solução é sua ou tem outra origem?
Pensei e implementei um O(n) e desisti de implementar a O(1) kkkkk
Qual o site que você usa para gravar esses vídeos?
Provavelmente excalidraw
Em linguagem Python, a utilização de in pode ser bastante útil para esses problemas.
Eu não sei se faz parte da regra eliminar a lista principal, ou alterar a numeração dos índices, mas se isso for permitido, uma ideia seria
while nums:
vari = nums.pop(0)
if vari in nums:
while vari in nums:
nums.remove(vari)
else:
break
Se a memória da lista precisar ficar intacta, um algoritmo que retorna o número de ocorrências de verificação linear poderia percorrer um a um:
for i in nums:
if nums.count(i) == 3:
continue
else:
return i
Se a lista poder ser semi alterada, você pode fazer uma brincadeira de ir jogando o item da frente para trás, mantendo-os na mesma lista, parando apenas no item único:
while True:
vari = nums.pop(0)
if vari in nums:
nums.append(vari)
else:
nums.append(vari)
return nums[-1]
ETC
Todas essas soluções tem complexidade de tempo quadrática e não linear como o exercício pede.
Na sua primeira solução: O método nums.remove percorre o vetor inteiro para encontrar o número a ser removido, como ele faz isso para cada valor do vetor então é O(n*n) = O(n^2)
Na sua segunda solução: método nums.count literalmente percorre o vetor inteiro contando quantas vezes o número aparece, logo se ele percorre o vetor 1 vez para cada número no vetor é O(n*n) = O(n^2)
Na terceira você usa "if vari in nums" para determinar se isso é verdadeiro ou falso ele percorre nums inteiro procurando a variável, logo se ele percorre o vetor uma vez para cada elemento então é O(n*n) = O(n^2)
Esse é um probleminha do python, usando as funções que ele tem implementado pode ficar difícil de perceber a eficiência do próprio código, por não saber como foi feita a implementação dessas funções.
@@Renan_PS-zt8lm Acredito que estamos tendo um erro de contextualização.
Por definição, "Linear Complexity" aumenta conforme a quantidade do input (tamanho do iterável lista[int]), a cada elemento. Em outras palavras, se um elemento tem 1 tempo para ser resolvido, se colocar 2 elementos o tempo de execução deve ser 2 tempos.
Logo, se para analisar 1 item ele leva 0.05 segundos, com 2 itens ele deve levar 0.10 segundos, e assim sucessivamente
Dentro do conceito de n², se eu aumentar 1 item, esse tempo multiplica. Ou seja, se um programa leva 0.05 segundos, com 2 itens ele leva 0.25 segundos, por causa dos protocolos de percorrimento.
Nos percorrimentos dos algoritmos apresentados, a execução do programa não se multiplica de n² por cada input a mais, são execuções de percorrimento simples.
Em outras palavras, se demora 0.10 segundos para encontrar o elemento único em uma lista com 10 elementos, é de complexidade linear que ele demore 1 segundo em uma lista com 100 elementos.
Um erro dos exemplos do qual eu entenderia a crítica seria "Mas no programa não pode alocar memória para responder, ou seja, criar variáveis", eu entenderia, e responderia algo mais simplório ainda:
while len(nums.count(nums[0])) == 3: nums.append(nums.pop(0))
return nums[0]
E assim nem variável seria utilizada.
Esse tipo de problema não é sobre agilidade de processamento, mas sim sobre algoritmo que não use muito memória, mesmo que demorado. Não necessariamente um algoritmo de Complexidade Linear é ágil, porém, mais ágil que outros.
@@TheRageOm O exercício específica que a complexidade de memória deve der constante e a complexidade de tempo tem que ser linear. O nums.count não descobre quantas vezes um elemento aparece no vetor magicamente, na implementação da função ele percorre o vetor inteiro e conta quantas vezes aparece. Ou seja, se você chama um nums.count (O(n)) para cada elemento do seu vetor (O(n)) a complexidade de tempo do algoritmo fica O(n^2).
Quando falamos da complexidade de memória, criar variáveis ou não não impacta na complexidade assintótica, a não ser que o número de variáveis cresça com o tamanho do vetor. Assintótica significa que constantes multiplicativas são desconsideradas, logo O(4627193) = O(1).
@@Renan_PS-zt8lm O problema é que você está interpretando que o script está lendo a lista. Ler a lista faz parte da subrotina. O conceito de O(n²) não é para scripts, mas sim para as consequências de adicionar mais ou menos elementos ao iterável.
Desta forma, ao adicionar 1 elemento, ela não aumenta o tempo linearmente, mas de forma exponencial. Isso ocorre com base no código, mas o conceito se aplica aos tamanhos dos iteráveis.
Vou dar um exemplo:
- uma str com len == 4
- cada caractere vai de a até z
- quantas formações aleatórias são criadas?
Caso eu aumente essa str para 5, aumenta consideravelmente, se for 6, ainda mais, etc
Isso não ocorre nos exemplos apresentados.
@@TheRageOm Nos seus exemplos, se a lista tiver 4 elementos vai demorar 16t, sendo t um intervalo de tempo constante arbitrário, agora se tiver 5 elementos vai 25t. Crescimento quadrático.
Não consigo entender a sintaxe de python ainda
dar sorted na lista e fazer um for que pula de 3 em 3, e parar quando achar um item da lista q o proximo dele não seja igual a ele seria uma maneira eficiente?
Não pq a operação sorted é cara, mas talvez o site aceite a resposta
Radix sort pode ter tempo linear em casos que a quantidade de dígitos não crescem significativamente com o tamanho da conjunto, que é o caso aqui. Realmente pode ser uma boa! Foda é lembrar como implementar de cabeça kkkkkkkk
Fui confirmar e não valeria por que o radix sort tem complexidade de espaço O(N) 😅
Já dizia um professor meu na universidade: "Olha a sacada dos caras"
o meu falava "Olha esse esquema dos caras", levo esse termo "esquema " pra vida toda
que difícil oq. é só fazer um map, com o elemento -> quantas vezes ele aparece e cabou. mete um if e já era😂
Não é só criar um map incrementando a quantidade caso já exista? Ou entendi errado?
No início do vídeo ele explica o porquê dessa solução não ser válida para o problema.
o problema tem uma restrição onde todo numero na array de input aparece exatamente 3 vezes, exceto o número que tentamos encontrar, que aparece apenas uma vez, pra mim é mais facil apenas usar um hashmap que mantém a quantidade de vezes encontramos um número e deletar do hashmap caso foi encontrado mais de 2 vezes, assim o unico numero que sobra no hashmap é o numero que aparece apenas 1 vez, acessar um numero no hashmap sempre será O(1) e dessa forma vc sempre corre pelo array 1 vez, ou seja, no final dá O(n) da mesma forma com um código imensamente mais compreensível
nem vi que era O(1) space 💀 achei bobo mas me pegou
Mas não usa alocação constante, usa alocação "dinamica"
Não vou resolver nem ver o vídeo mas tragoa solução. Ao invés de procurar o unico elemento é só procurar os elementos repetidos pois é muito mais fácil. Depois de encontrar todos é só eliminar e ficar com o restante. se for apenas 1 numero único, você ficará com o único, se forem algums vc ficará com algums.
Eu resolvi de maneira pais pragmatica... conta os bits numa lista. Faz mod 3 na lista depois reconstroi o numero. A complexidade e identica ja que o tamanho do inteiro e constante, porem nao tem magia nenhuma. O lado bom da solucao por contagem de bits e que da pra fazer pra qualquer numero de repeticoes sem nenhum problema, sei la, 7 repeticoes.
mano, vc consegue deixar o audio do video um pouco mais alto?
Não
Aumenta o volume
Eu uso uma extensão chamada soundFixer, recomendo usar ela também. É possível aplicar ganho nos áudios do navegador de até 5 (500%)
Pra que
Foi irônico? Pra mim parecia alto demais kkk
Muito elegante!
Qual é o uso prático do conhecimento requisitado por esse desafio?
Qual aplicativo usa para gravar a tela e mexer a webcam assim
OBS Studio
@@TheDenysabner N tenho certeza, pq ele mexe a camera arrastando com o mouse
@@user-gr7rp6fj8w isso é normal no OBS
Como alguem chega em uma solucao como essa??
?Ha alguma generalizacao pra n repeticoes
Pior que existe sim. Mas esse já foi difícil de explicar kkk
Acho que é mais fácil de entender se fazer
twos ^= num & ones;
ones ^= num & ~twos;
Trocando a ordem voce pode verificar o ones anterior para utilizar no twos
em javascript pensei dessa forma:
let nums = [2, 2, 1, 2];
const findSingleNumber = () => {
let single;
nums.forEach(num => {
const filterLength = nums.filter(itemNum => itemNum === num);
if (filterLength.length === 1) {
single = filterLength[0];
}
})
console.log(single)
}
findSingleNumber();
po essa solução é matemática computacional puro
Praticamente uma máquina de turing kkkkkkkkk
Já existe uma palavra em português para "to track": rastrear.
ta sussurrando kkkkkkkk
Essa questão ser classificada como "medium" é sacanagem kkkkkkkkkkkkk. E teu áudio tá baixo, tenho que sair do volume 20 pro 50 pra poder escutar bem.
Fiz assim, mas n li direito as regras rs, mas é bem legal o desafio
const number2 = array.find(i => { if (array.filter(j => j === i).length === 1) return i })
ou assim
const number = array.find(i => { if (array.filter(j => j === i).length !== 3) return i })
questão mto legal
Isso aqui passa no sistema que vc ta usando?
private static void Main(string[] args)
{
int[] lista = { 21, 7, 22, 7, 2, 3, 2, 7, 3, 5, 6, 21, 8, 6 , 10, 5, 17, 10, 11, 12, 200, 11, 200, 12, 17, 22 };
Array.Sort(lista);
bool duplicado = false;
int solucao = lista[0];
for (int i = 0; i < lista.Length; i++)
{
if (lista[i] == lista[i + 1])
{
duplicado = true;
}
else if (duplicado == false)
{
break;
}
else
{
solucao = lista[i + 1];
duplicado = false;
}
}
Console.WriteLine(solucao);
Console.ReadLine();
}
youtube premium ótimo vídeo
Não assisti o vídeo (ainda) e resolvi o problema usando o thumbnail com javascript. Não sei as especificações e provavelmente existem formas melhores de se fazer, mas levei uns 3 minutos pra fazer:
let a = [2,7,7,2,3,2,7]
let b = [];
a.forEach(item => {
if(a.filter(i => i === item).length === 1) b.push(item)
});
enfim, com certeza da pra melhorar isso, mas é funcional.
Essa solução não utiliza alocação "fixa" pois tem DUAS listas. (uma é a variavel b e a outra é o retorno do metodo filter)
@@ZantsuRocks como eu disse, nao tinha visto o video, so o thumbnail.
@@ZantsuRocks Sim, mas essa soluçao resolve quando tem multiplos itens nao repetidos... Se nao quer, so retornar o item em vez de dar push....
@@TalesIagoBatista Na verdade não, o return dentro do metodo forEach "não faz nada", ele vai seguir executando o forEach até o fim
Legal a solução pensei em algo bem parecido
const number = array.find(i => { if (array.filter(j => j === i).length === 1) return i })
cara gostei bastante desse canal, pois diferentemente dos outros canais que tem hoje em dia que só falam coisas basicas e vendem mentiras (tipo com 6 meses vc conseguir trampo pra ganhar 10k) esse canal aborta leet code e praticas de software que me agregaram, continue assim
Verdade esse é um grande diferencial
meu parcerinho que programa/site é esse do fundo preto??
vscode
@@PintoDonald kkkkkkk obg mano, mas me referi a o programa q ele "desenha" a lista, as setas e afins
@@zec_s ops kkkkk
@@zec_s Não sei se você já chegou a descobrir, mas se caso não o website usado é o Excalidraw.
@@HIM-br9qy obrigado
Qual o site dos desafios?
leetcode
cara, é so fazer manipulação de arquivo ue, tu pega um numero e coloca no arquivo e ordena por la ou faz o count la.
ele explicitou em memoria e não memoria secundaria/armazem externo
Se vc usar essa forma, vc com certeza adicionará no mínimo Time Complexity pra ler ou ordenar o arquivo. E Space Complexity não depende de onde seus dados estão, o fato de vc usar memória adicional dependente do tamanho do array já viola a complexidade de espaço. A resolução mostrada no vídeo cumpre ambas as soluções de complexidade de tempo e espaço.
Que site é esse aonde você pegou o desafio?
Leetcode
que vídeo insanoooooooooooooooooooooo
Esses problemas geralmente são para serem resolvidos com a menor complexidade possível, mas a solução em si é facil, só agrupar os valores e pegar o com Count/Length == 1 kkkkkkkk
Pensei nisso, só um if e um return resolvia, n sei se em python o count é Implementado em c
Em c# daria pra resolver fazendo um Array.Sort(nums), e depois um for comparando o nums[i] com o nums [i+1], se for >< pronto, resolveu.
@@seveng0th Não daria, a função de sort não é executada em tempo linear, acho que a implementação do C# e de muitas outras linguagens é de O(n log(n))
Agrupar os valores faz a complexidade de espaço não ser mais O(1) pois o tamanho desses valores agrupados dependerá do tamanho do array fazendo sua solução ter complexidade espacial O(N) e não O(1) que é um dos requisitos do problema.
Em Js é tao simples:
const list = [2,1,1,2,2,3,3,4,4,5]
let one = false;
for (const num of list){
const achou = list.filter((p)=> p===num).length;
if(achou === 1)one=num;
}
// Log to console
console.log('One:',one)
@ZantsuRocks a sim, por isso eu indiquei essa soluçao...
Fiz assim com Js
const singleNumber = (nums) => {
const [num] = nums.filter(
(num) => nums.indexOf(num) === nums.lastIndexOf(num)
);
return num;
}
Isso é super facil. Ordena os elementos do array em ordem crescente e faz um for, se array[i] for diferente de array[i+1], fim, achou.
Pensei nisso, problema de ordenar é que a memória vai ser alterada dinamicamente (vai ser alocado na memória uma nova variável com o mesmo tamanho do input), exceto que fabrique teu próprio código para ordenar manipulando/destruindo a variável de entrada
Eu esqueci de mencionar no vídeo, mas isso quebra outra premissa do problema. Precisa ter linear runtime complexity, ou seja, rodar em O(n). ordenar é n log n
@@GutoGalego com O(n) acho que dá pra fazer com um for e um while, vou tentar e jaja replico aqui.
conseguiu?@@seveng0th
Cara, isso é de boa, as questões dificeis do leetcode tem constraints bem mais difícieis que essa
De boa... Beleza raspador de bits
como brincadeira isso é mto legal mesmo. o foda é usarem essas paradas em entrevistas, ou tipo o caso do primeiro comentário que perdeu o emprego pq não fica fazendo essas porras. dai o cara sabe leetcode e não sabe estruturar um código legível, ou debugar algo complexo, nem entro no mérito de quais arquiteturas de software usar para cada problema. tipo, tu só seleciona gente com tempo e paciência para ficar brincando, que não necessariamente vai adicionar numa empresa.
Isso nunca será um problema pra big techs. Eles tem dinheiro de sobra pra queimar treinando seus funcionários e tão pouco se importando se você tem habilidades em escrita de código legível e habilidades pra debugar códigos complexos. Eles não precisam disso, eles tem a comunidade open source pra debugar e melhorar o código se for necessário. A regra é que código é descartável, e os projetos que eles desejam manter por muito tempo vira open source, e toda a comunidade que usa código faz esse trampo que você falou.
"tu só seleciona gente com tempo e paciência para ficar brincando".
É esses caras que eles precisam. Se alguém surge com uma ideia que vai de algum modo contribuir com o modelo de negócio ou estratégia do conglomerado, é desses caras que tiveram tempo pra ficar brincando com peculiaridades de complexidades e firulas de algoritmos que eles precisam pra fazer o bagulho funcionar.
De acordo com o livro do Google, a primeira versão do rankeador era um lixo de código. Foi reescrita várias vezes (do zero) durante os primeiros anos do google. Mas ainda assim o valor que esses ranqueador entregava já era anos luz a frente dos concorrentes.
3 em binário é 11
som é muito baixo
`input = [2,2,3,2]
def single_number(arr):
if len(arr) == 0:
return 0
else:
if len(arr) == 1:
return arr[0]
else:
return arr[0] if arr[0] not in arr[1:] else single_number(arr[1:])
print(single_number(input))`quando resolvi sem ver o vídeo fiz assim e nem percebi que era O(1)
No pior caso, ele vai executar essa operação IN uma vez pra cada elemento do array, ou seja, no final a complexidade não é linear e sim quadrática. E acredito que o uso de slice como arr[1:] também crie uma lista em memória pra fazer a comparação, então acho que também acaba que não fica O(1) a complexidade de espaço
@@michaelnicholas926 isso que quis dizer, nem percebi que a questão queria O(1) o meu caso, no pior seria O(n^2), não?
@@derkonig7820 Em relação a espaço, eu acho que a lista que a função slice cria só é usada na operação do IN e depois é excluida então creio que seja O(n) (me corrige se estiver errado kkkk), mas em relação a complexidade de tempo é n^2 sim no pior caso
Esse problema é bem simples, é só rodar um for na lista e criar outra lista com as frequências de cada elemento na lista principal, depois você saberá quais elementos tem na lista e quantas vezes eles se repetiram
3 não é 110
Já que o anjo de Deus não se deu ao trabalho de corrigir:
3 em binário não seria 110 e sim 11.
#ajudei
Eu usaria um vetor de 31 bits
E contaria bit a bit
Sua solução é maneira
class Solution {
public:
int singleNumber(vector& nums) {
vector vet(32);
int res = 0;
for(int i = 0; i < nums.size(); i++){
for(int j = 0; j < 32; j++){
if((nums[i] & (1
isso funcionaria?
class Solution:
def singleNumber(self, nums: List[int]) -> int:
for j in range(len(nums)):
x = 0
for i in range(len(nums)):
if nums[j] == nums[(-i-1)] and ((-i-1)+len(nums)) != j:
x = 1
if x == 0:
y = nums[j]
return y
Acredito que não, pois nesse algoritmo a verificação se daria por matriz de ij, sendo que é dito nas restrições que todas as réplicas de int aparecem três vezes, exceto um (que aparece uma única vez).
Ao longo da análise, y armazenaria apenas o que não apareceu 2 vezes na matriz.
Mas, e se x == 1? Logo, o código nunca resolveria o valor de y, dando erro de execução. Esse erro, apesar de parecer impossível, deve ser evitado, pois existe uma probabilidade dele acontecer (lista int com apenas um valor).
Outra restrição é que a análise deve ser feita em tempo O(n), ou seja, o tempo por item deve crescer de forma linear com o tamanho de itens. Nessa execução, seria algo mais parecido O(n²), por se tratar de análise em matriz, deixando o tempo o quadrado de tempo a ser analisado
Então acredito que sim, pode funcionar, mas para o problema é inviável segundo os requerimentos.
Achei a parte do FOR com IF meio complicada. Preferi assim:
nums = [0,1,0,1,0,1,99]
nums2 = [2,2,3,2]
x = [n for n in nums if nums.count(n) ==1]
y = [n for n in nums2 if nums2.count(n) ==1]
print(*x)
print(*y)
Entao, mas esse é ponto desse video, ele sabe que essa é a solucao mais facil e rapida de se pensar, mas o problema quer que voce resolve em O(1) ou seja ele nao quer que voce percorra o array mais de uma vez, que é o que voce esta fazendo em .count()
@@MrZ1kaO problema quer O(1) em espaço, então o problema não é percorrer o array mais de uma vez, o problema é ter um array cujo tamanho depende da entrada
@@samon101mas ainda tem que ter tempo linear. Não manjo muito de python, mas essa operação aí não é n^2 por causa do count() dentro de um loop?
Caraca, fritei o cerebelo mas ACHO que entendi. Eu estudo Python a algum tempo, mas as operações que geralmente uso são "not", "and" e "or". É a primeira vez que vejo esses operadores |, ^, ~ sendo usados em um programa. Qual o nome desse assunto pra eu poder estudar?
Bitwise Operators
Impossivel??? O que é isso então?
let toCheck = [1, 1, 3, 2, 3, 1, 3, 1, 4, 2];
for (let i = 0; i < toCheck.length; i++) {
let qtd = 1;
for (let j = 0; j < toCheck.length; j++) {
if (j === i) continue;
if (toCheck[i] === toCheck[j]) {
qtd++;
break;
}
}
if (qtd === 1) {
console.log(toCheck[i]); //Aqui é o return, inclusive pode tirar o break
break;
}
}
Na descrição do problema diz que precisa ser em tempo linear. Ou seja, O(n). Eu esqueci de deixar isso mais claro no meu vídeo. Esse é o motivo que não da pra resolver com .sort() por exemplo também
@@GutoGalego Não tem sort na minha solução. Mas tbm não é linear.
Eu sei que não. Mas for i.... for j são duas iterações sobre o array. Isso faz com que ela seja O(n2) e não O(n). O motivo que não da pra usar essa é o mesmo motivo que não dá pra usar sort. A complexidade temporal precisa ser O(n), não da pra fazer loop dentro de loop@@ZantsuRocks
cara eu achei na verdade esse exercício nível fácil pra ser sincero com um simples sort e um loop for voce resolve.
PS: eu sou programador a 9 meses e resolvi em menos de 20 minutos dessa forma.
Runtime:55ms Beats 67% | JS Users
Memory:49.77MB Beats 71% | JS Users
var singleNumber = function(nums) {
let n = nums.sort((a, b) => a-b);
var saw=n[0];
for(let i = 1; i < n.length; i++){
if(n[i+1] == undefined){
if(n[i] != saw && n[i] != n[i-1])saw=n[i]
}else {
if(n[i] != saw && n[i+1] != n[i] && n[i] != n[i-1])saw=n[i]
}
}
return saw;
};
Lembrando que essa estrutura foi feita por um iniciante e mantem a estrutura O(1) e armazena apenas um valor independente do tamanho de nums
Quebra premissa do problema, tem que resolver em complexidade temporal linear, sort é O n log n. Eu sei que passa no leetcode, mas numa entrevista por exemplo não ia passar
@@GutoGalego desculpa você está certo pedi ajuda pra um senior pra entender o que você disse vou mexer no código amanha e ver se arrumo obrigado !
@@GutoGalego bom sábado pra você. eu acordei tem alguns minutos e decidi refazer o código dessa vez levou menos de 10 minutos poderia confirmar pra mim se agora está em O(n)?
var singleNumber = function(nums) {
let n = nums.sort((a, b) => a-b);
var saw=n[0];
var count=1;
for(let i = 1; i < n.length; i++){
if(n[i] == saw){
count++;
i++;
}else if(n[i] != saw){
if(count > 1){
count=1;
saw = n[i];
}
}
}
return saw;
};
eu percorro uma vez e apenas verifico se o numero já foi visto caso sim. eu pulo um a mais e continuo verificando. Se puder me ajudar eu ficaria grato no leetcode passou tambem
∅
Bem, li o titulo, me senti meio intrigado, entrei no vs code e criei um script em python...:
lista = [2, 7, 7, 2, 3, 2, 7]
counter = {}
for i in lista:
if i not in counter:
counter[i] = 1
elif i in counter:
counter[i] += 1
print(counter)
Deu certo. Talvez em outra linguagem, tipo C, talvez nao conseguiria implementar desse jeito. Mas enfim, sou um mero aprendiz, hehe.....
Nessa solução o seu counter faz o seu algoritmo ter complexidade espacial O(n) em vez de O(1).
Vc precisa de uma solução que não aloque memória que dependa do tamanho do array inicial.
Interessante a solução, porém acredito que a primeira abordagem estava correta. O espaço não vai ser O(n) pois ele não cresce de acordo com a quantidade de elementos mas sim com os valores que o array pode conter, que de acordo com a questão varia entre -2³¹ e 2³¹-1. Dessa forma, independente da quantidade de elementos, o dicionário terá um tamanho constante pois ele irá armazenar valores e não elementos do array.
Apenas 1% dos devs "consegue" resolver. Que falta faz o primário!
Está correto utilizar "consegue", pois "1%" é singular. Que falta faz o secundário 🤭🤭
www.tjsc.jus.br/web/servidor/dicas-de-portugues/-/asset_publisher/0rjJEBzj2Oes/content/como-concordar-frases-com-percentual-ou-porcentual-
De nada amigão, recebeu aula de software, de português e aprendeu a não ser pedante, principalmente quando não sabe do que ta falando.
Mas ele está correto, pois o consegue se refere ao problema, e não aos desenvolvedores.
@@TheRageOm tá doido? Consegue concorda com o sujeito, que no caso seria "1%"
@@felipe.raposo eu nem entendi se é meme ou não o que esse cara ta falando KKKKKKK. Só sei que o que fez o comentário original é o tipo de pessoa mais insuportável da internet. O desnecessariamente pedante. No caso agora ele ficou bem quietinho e sumiu pq ele percebeu que ele tava errado e passou altas vergonha.
Só registrando minha solução de iniciante coda fofo no início do vídeo: criaria um novo array e uma função em loop para verificar o próximo item do array principal, se for diferente dos itens anteriores adicionaria o valor ao novo array, se não, sendo igual a algum anterior excluiria do novo array. Acho que usaria find pra vasculhar o array, e um for loop pra função, mas confesso que nem sei certo de cabeça como implementaria pra funcionar
tbm faria assimkkkkkkkkkkkkkk