编程知识 cdmana.com

Introduction à l'algorithme "dénombrement binaire" simple 04 - leetcode 1346. Vérifier si les entiers et leurs doubles existent

Un.、Titre

1、Description du sujet

  Pour vous donner un tableau entier arr,Veuillez vérifier s'il y a deux entiers N Et M,Satisfaction N - Oui. M Deux fois plus.(C'est - à - dire:,N = 2 * M).
  Exemple d'entrée: arr = [10,2,5,3]
  Exemple de sortie: true

2、Cadre de base

  • CLangues La version donne les codes - cadres de base suivants:
bool checkIfExist(int* arr, int arrSize){
    }

3、Lien vers la question originale

LeetCode 1346. Vérifiez l'existence d'entiers et de leurs doubles

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

1、Analyse des idées

   Trier d'abord pour qu'il soit ordonné , Puis énumérez un nombre , Cherchez à gauche si c'est deux fois plus , À droite, deux fois plus .

2、Complexité temporelle

   La complexité temporelle est principalement due au tri ,La complexité temporelle totale est O ( n l o g 2 n ) O(nlog_2n) O(nlog2n).

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 search(int* nums, int n, int target){
    
    int r = binarySearch(nums, n, target);
    if(r == n || nums[r] != target)
        return -1;
    return r;
}

int cmp(const void *a, const void *b) {
    
    return *( (int *)a ) - * ( (int*)b );
}

bool checkIfExist(int* arr, int arrSize){
    
    qsort(arr, arrSize, sizeof(int), cmp);                  // (1)
    int i, pos, base; 
    for(i = 0; i < arrSize; ++i) {
                   
        base = i+1;
        pos = search(arr+base , arrSize-base, 2*arr[i]);    // (2)
        if(pos != -1) {
    
            return true;
        }
        pos = search(arr , i, 2*arr[i]);                    // (3)
        if(pos != -1) {
    
            return true;
        }
    }
    return false;
}
  • ( 1 ) (1) (1) Trier;
  • ( 2 ) (2) (2) Deux fois plus à droite ,Retour trouvé;
  • ( 3 ) (3) (3) Il peut y avoir un nombre négatif , C'est pour ça qu'on cherche aussi à gauche ,Retour trouvé;

Trois、Petite connaissance de ce sujet

   Les tableaux ordonnés sont généralement préférés Recherche binaire. Pas un tableau ordonné , Faites - le d'abord en ordre .


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/20211014005732321g.html

Scroll to Top