Soit Code Jour 64 à partir de zéro "287. Trouver le numéro en double"

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est de mettre en œuvre des fonctions et des classes spécifiques en fonction du thème.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage qui est effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à l'époque sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 63 "195. Dixième ligne" à partir de zéro

À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

287. Find the Duplicate Number

Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées.

Le problème est que, si on donne un tableau «nums» contenant n + 1 entiers où chaque entier est compris entre 1 et n, prouver qu'il doit y avoir au moins un nombre en double. .. Concevez un algorithme pour trouver le nombre de doublons, en supposant qu'il n'y a qu'un seul doublon.

Example 1: Input: [1,3,4,2,2] Output: 2

Example 2: Input: [3,1,3,4,2] Output: 3

Note: Ne modifiez pas le tableau (en supposant que le tableau est en lecture seule). Seul l'espace supplémentaire de la constante O (1) doit être utilisé. La complexité d'exécution doit être inférieure ou égale à O (n2). Il n'y a qu'un seul doublon dans le tableau, mais il peut être répété plusieurs fois.

Solution

N'oubliez pas qu'il est en lecture seule et ne peut pas être trié.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low,high = nums[0],nums[nums[0]]
        while low != high:
            low,high = nums[low],nums[nums[high]]
        low = 0
        while low != high:
            low,high = nums[low],nums[high]
        return low
# Runtime: 64 ms, faster than 86.19% of Python3 online submissions for Find the Duplicate Number.
# Memory Usage: 16.4 MB, less than 35.59% of Python3 online submissions for Find the Duplicate Number.

Low est la réponse en ayant des éléments en "bas" et en "haut" respectivement et en continuant à remplacer les éléments en nombres en remplaçant 0 par bas et en répétant.

C'est peut-être une solution un peu insatisfaisante, mais cette fois c'est à ici. Je vous remercie pour votre travail acharné.