编程知识 cdmana.com

Introduction à l'algorithme simple 06 - - leetcode 34. Trouver la première et la dernière position d'un élément dans un tableau de tri

Un.、Titre

1、Description du sujet

  Compte tenu d'un tableau entier dans l'ordre croissant nums,Et une valeur cible target.Trouver la position de départ et de fin d'une valeur cible donnée dans le tableau.Si la valeur cible n'existe pas dans le tableau target,Retour [-1, -1].
  Exemple d'entrée: nums = [5,7,7,8,8,10], target = 8
  Exemple de sortie: [3,4]

2、Cadre de base

  • CLangues La version donne les codes - cadres de base suivants:
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    }

3、Lien vers la question originale

LeetCode 34. Trouver la première et la dernière position de l'élément dans le tableau de tri

2.、Rapport de résolution de problèmes

1、Analyse des idées

  Tableau de partition, ≥ t a r g e t \ge target target Le nombre est vert , Le reste est rouge . Deux minutes pour trouver la frontière verte , Si la limite verte n'est pas égale à n n n Et La valeur de la position correspondante est égale à t a r g e t target target, Continue à chercher. ≥ t a r g e t + 1 \ge target+1 target+1 La limite rouge de ( C'est - à - dire la limite verte moins un ), Retourner aux deux limites est la réponse ;Sinon,Retour [ − 1 , − 1 ] [-1, -1] [1,1].

2、Complexité temporelle

  La complexité temporelle totale est O ( l o g 2 n ) O(log_2n) O(log2n).

3、Détails du Code


/************** Recherche binaire Tableau Modèle **************/
/* 1)Le tableau des paramètres de transfert satisfait:Rouge rouge rouge rouge rouge rouge vert Vert Vert Vert; 2)Valeur de retour:Limite gauche de la section verte; */

int isGreen(int val, int x);

int binarySearch(int *arr, int arrSize, int x) {
    
    int l = -1, r = arrSize;
    int mid;
    while(l + 1 < r) {
    
        mid = l + (r - l) / 2;
        if( isGreen(arr[mid], x) )
            r = mid;
        else
            l = mid;
    }
    return r;
}
/************** Recherche binaire Tableau Modèle **************/

int isGreen(int val, int x) {
    
    return val >= x;
}
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    
    int l, r;
    int *ret = (int *)malloc( sizeof(int) * 2 );
    *returnSize = 2;
    l = binarySearch(nums, numsSize, target);       // (1)
    if(l == numsSize || nums[l] != target) {
            // (2)
        ret[0] = ret[1] = -1;
        return ret;
    }
    r = binarySearch(nums, numsSize, target+1) - 1; // (3)
    ret[0] = l;
    ret[1] = r;
    return ret;
}
  • ( 1 ) (1) (1) Trouver plus ou moins t a r g e t target target Indice minimal de ;
  • ( 2 ) (2) (2) Rien trouvé , Retour direct à deux -1;
  • ( 3 ) (3) (3) Trouver plus ou moins t a r g e t + 1 target+1 target+1 Indice minimal de ,Moins1 C'est la limite droite ;

Trois、Petite connaissance de ce sujet

   Les tableaux ordonnés sont généralement préférés Recherche binaire.


Quatre、Instructions pour l'ajout de groupes

  Je crois que la plupart de mes articles sont「 Étudiants 」,Tous ceux qui peuvent aller à l'Université sont「 Elite 」,Alors naturellement, nous devons「 L'excellence 」,Si vous êtes toujours「 Première année 」,C'est super,Tu as beaucoup de temps,Bien sûr que tu as le choix.「 Drama de brosse 」,Et pourtant,「 Apprendre les algorithmes 」,Trois ans plus tard, vous serez naturellement「 On ne peut pas parler en même temps 」.
  Alors, ici.,J'ai rangé「 Des dizaines d'algorithmes de base 」 Classification de,Cliquez pour ouvrir:

Guide de démarrage de l'algorithme

  Si le lien est masqué,Ou avoir des problèmes de permission,On peut parler à l'auteur.

  Aperçu de l'ensemble de questions:


Insérer la description de l'image ici


  Pour rendre ça intéressant,Et「 Prendre soin des débutants 」,À l'heure actuelle, seuls les algorithmes les plus simples sont ouverts 「 Série ENUM 」 (Y compris::énumération linéaire、Double pointeur、Préfixe et、Dénombrement binaire、Dénombrement trigonométrique),Oui. La moitié des membres ont fini. 「 Série ENUM 」 Après toutes les questions,Ouvre le chapitre suivant,Quand tout sera fini.,Tu es toujours dans le Groupe.,Alors tu seras「 .Algorithme d'écriture silencieuse tard dans la nuit 」Groupe d & apos; experts Un membre de.
  Ne sous - estimez pas ce groupe d'experts,Trois ans plus tard,Tu seras quelqu'un d'autre. C'est impossible. L'existence de.Si vous voulez rejoindre,Vous pouvez me contacter,Vu que tout le monde est étudiant, Non.「 Principales sources économiques 」,Sur le chemin de devenir Dieu,「 Je ne demande rien. 」.
  Contacter l'auteur,Ou scanner la page d'accueil de l'auteur Code QR plus Groupe,Joignez - vous à nous.


Il n'y a pas d'algorithmes difficiles à apprendre

CTutoriels d'animation gratuits en langue,Frappe avec moi!
La photoastronomieCLangues

Niveau d'entréeCRésumé des vrais problèmes linguistiques
🧡《CIntroduction à la langue100Exemple》🧡

Quelques diagrammes apprennent une structure de données
Dessiner la structure des données

Apprentissage en groupe,Croissance de la masse
Guide de démarrage de l'algorithme

Tutoriel d'images et de textes de la médaille d'or du concurrent
.Algorithme d'écriture silencieuse tard dans la nuit

版权声明
本文为[Où est le héros?]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211014005732309u.html

Scroll to Top