编程知识 cdmana.com

Introduction à l'algorithme "dénombrement binaire" modéré 01 - - question d'entrevue leetcode 10.09. Recherche de matrice de tri

Un.、Titre

1、Description du sujet

  Compte tenu de m × n m \times n m×n Matrice,Chaque ligne、Chaque colonne est en ordre croissant,Écrivez le Code pour trouver un élément.
  Exemple d'entrée: numbers = [[2,7],[11,15]], target = 11
  Exemple de sortie: true

2、Cadre de base

  • CLangues La version donne les codes - cadres de base suivants:
bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){
    }

3、Lien vers la question originale

LeetCode Questions d'entrevue 10.09. Recherche de matrice de tri

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

1、Analyse des idées

   Modèle de tableau avec recherche binaire . énumérez d'abord une ligne de la matrice , Pour chaque ligne, utilisez un dénombrement binaire distinct pour l'énumération .

2、Complexité temporelle

   La complexité temporelle de la tenue des pièces est O ( m ) O(m) O(m),La complexité temporelle de la recherche binaire est O ( l o g 2 n ) O(log_2n) O(log2n),La complexité temporelle totale est O ( m l o g 2 n ) O(mlog_2n) O(mlog2n).

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;
}

bool searchMatrix(int** matrix, int matrixSize, int matrixColSize, int target){
    
    int i;
    for(i = 0; i < matrixSize; ++i) {
    
        if(-1 != search(matrix[i], matrixColSize, target) ) {
    
            return true;
        }
    }
    return false;
}

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/20211014010924280w.html

Scroll to Top