C++-Programm zum Zählen der Anzahl der Array-Elemente, die größer als alle Elemente links davon sind und mindestens K Elemente rechts davon haben

Eine Zeichenfolge ist ein Objekt, das eine Folge von Datenzeichen darstellt. Strings sind Datencontainer, die immer im Textformat dargestellt werden. Es wird auch für Konzept-, Vergleichs-, Teilungs-, Verbindungs-, Ersetzungs-, Trimm-, Längen-, Internierungs-, Gleichheits-, Vergleichs- und Teilzeichenfolgenoperationen verwendet. Die K größten (oder kleinsten) Elemente in einem Array unter Verwendung des Quicksort-Partitionierungsalgorithmus.

Dies ist ein Array R[], das N verschiedene Ganzzahlen enthält. Die Aufgabe besteht darin, das spezifische Element zu finden, das strikt größer als alle Elemente davor und strikt größer als mindestens K Elemente rechts davon ist. Die Frage besagt, dass ein Array arr[ ] (Array R) aus N verschiedenen Elementen und einer ganzen Zahl K besteht. Wir müssen die Anzahl der Elemente ermitteln, die größer als alle Elemente auf seiner linken Seite sind und mindestens K Elemente auf seiner rechten Seite haben .

Input: R[] = {16,07,10,22,2001,1997}, K = 3
Output: 16
Therefore, the count is 2.

Es gibt zwei Möglichkeiten, Array-Elemente zu finden, die größer als alle Elemente auf der linken Seite und mindestens K Elemente auf der rechten Seite sind.

• Naive Methode – Dies ist die einfachste Möglichkeit, über ein bestimmtes Array zu iterieren. Bei dieser Methode müssen wir alle Elemente nach links durchlaufen, um zu prüfen, ob sie kleiner sind. Andernfalls gehen Sie nach rechts und prüfen Sie, ob die kleinsten K-Elemente kleiner sind. Für diesen Ansatz beträgt die Zeitkomplexität O(N2) und der Hilfsraum O(1).

• Effiziente Methode – Dies ist ein Optimierungsprozess, der mit einem selbstausgleichenden BST durchgeführt werden kann. Durchlaufen Sie das Array einzeln von rechts nach links durch den AVL-Baum. AVL Tree generiert ein Array countSmaller[]. Hier ist die Zeitkomplexität O(NlogN) und der Hilfsraum ist O(N). Erhöhen Sie die Anzahl für jedes Element, das die Bedingung erfüllt.

Finden wir die Anzahl der Array-Elemente, die größer ist als alle Elemente links davon und mindestens K Elemente rechts davon.

Algorithmus zum Zählen von Array-Elementen, die größer als alle Elemente sind:-

In diesem Algorithmus folgen wir dem Schritt-für-Schritt-Prozess zum Zählen der Anzahl der Array-Elemente. Damit erstellen wir etwas C++-Code, um das größte Element unter allen Elementen zu finden.

• Schritt 1 – Los geht’s.

• Schritt 2 – Durchlaufen Sie das Array von rechts nach links.

• Schritt 3 – Fügen Sie alle Elemente in den AVL-Baum ein.

• Schritt 4 – Array countSmaller[] mithilfe des AVL-Baums generieren.

• Schritt 5 – Es enthält die Anzahl des kleineren Elements rechts von jedem Array-Element.

• Schritt 6 – Durchlaufen Sie das Array und finden Sie jedes Element.

• Schritt 7 – Überprüfen Sie, ob dies der bisher erhaltene Maximalwert ist und ob countSmaller[i] größer oder gleich K ist.

• Schritt 8 – Wenn die Bedingung erfüllt ist, erhöhen Sie die Anzahl.

• Schritt 9 – Drucken Sie den Endwert von count als Antwort aus.

• Schritt 10 – Kündigung.

Grammatik

for (i = k; i < array.length; i++){
minIndex = 0;
for (int j = 0; j < k; j++){
   if(array[j] < array[minIndex]){
      minIndex = j;
      array[minIndex] = array[j];
   }
}
if (array[minIndex] < array[i]){
   int temp = array[minIndex];
   array[minIndex] = array[i];
   array[i] = temp;
}

Hier ist eine Ganzzahl-Array-Nummer, die Ganzzahl ist K. Es wird das K-te Element im Array zurückgegeben. Wir müssen es in O(n)-Zeitkomplexität lösen.

Methode

• Methode 1 – Finden Sie die K größten (oder kleinsten) Elemente mithilfe der Sortierung.

• Methode 2 – Effiziente Möglichkeit, die K größten (oder kleinsten) Elemente in einem Array zu finden.

Finden Sie K größte (oder kleinste) Elemente mithilfe der Sortierung

Wir können das Ergebnis dieses Problems durch Sortieren erhalten. Hier sind die Schritte -

• Elemente in absteigender Reihenfolge sortieren.

• Drucken Sie die ersten K-Zahlen in diesem sortierten Array.

Beispiel 1

#include <bits/stdc++.h>
using namespace std;
void kLargest(int arr[], int a, int b){
   sort(arr, arr + a, greater<int>());
   for (int i = 0; i < b; i++)
   cout << arr[i] << " ";
}
int main(){
   int arr[] = { 10, 16, 07, 2001, 1997, 2022, 50 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   kLargest(arr, n, k);
}
</int>

Ausgabe

2022 2001 1997 

Effiziente Möglichkeit, die K größten (oder kleinsten) Elemente in einem Array zu finden

Bei dieser Methode befolgen wir die folgenden Schritte, um das Ergebnis herauszufinden -

• Starten.

• Durchlaufen Sie das Array von rechts nach links.

• Fügen Sie alle Elemente in den AVL-Baum ein.

• Generieren Sie das Array countSmaller[].

• Die Anzahl des kleineren Elements rechts von jedem Array-Element.

• Wenn es sich um den Maximalwert handelt, ist countSmaller[i] größer oder gleich K.

• Dann erhöhen Sie die Anzahl.

• Drucken Sie den Wert aus.

• Das Ende.

Beispiel 2

#include <bits/stdc++.h>
using namespace std;
struct node {
   int key;
   struct node* left;
   struct node* right;
   int height;
   int size;
};
int max(int a, int b);
int height(struct node* N){
   if (N == NULL)
   return 0;
   return N->height;
}
int size(struct node* N){
   if (N == NULL)
   return 0;
   return N->size;
}
int max(int a, int b){
   return (a > b) ? a : b;
}
struct node* newNode(int key){
   struct node* node
   = (struct node*)
   malloc(sizeof(struct node));
   node->key = key;
   node->left = NULL;
   node->right = NULL;
   node->height = 1;
   node->size = 1;
   return (node);
}
struct node* rightRotate(struct node* y){
   struct node* x = y->left;
   struct node* T2 = x->right;
   x->right = y;
   y->left = T2;
   y->height = max(height(y->left),
   height(y->right))
   + 1;
   x->height = max(height(x->left),
   height(x->right))
   + 1;
   y->size = size(y->left)
   + size(y->right) + 1;
   x->size = size(x->left)
   + size(x->right) + 1;
   return x;
}
struct node* leftRotate(struct node* x){
   struct node* y = x->right;
   struct node* T2 = y->left;
   y->left = x;
   x->right = T2;
   x->height = max(height(x->left),
   height(x->right))
   + 1;
   y->height = max(height(y->left),
   height(y->right))
   + 1;
   x->size = size(x->left)
   + size(x->right) + 1;
   y->size = size(y->left)
   + size(y->right) + 1;
   return y;
}
int getBalance(struct node* N){
   if (N == NULL)
   return 0;
   return height(N->left)
   - height(N->right);
}
struct node* insert(struct node* node, int key,
int* count){
   if (node == NULL)
      return (newNode(key));
   if (key < node->key)
      node->left = insert(node->left, key, count);
   else {
      node->right = insert(node->right, key, count);
      *count = *count + size(node->left) + 1;
   }
   node->height = max(height(node->left),
   height(node->right))
   + 1;
   node->size = size(node->left)
   + size(node->right) + 1;
   int balance = getBalance(node);
   if (balance > 1 && key < node->left->key)
   return rightRotate(node);
   if (balance < -1 && key > node->right->key)
   return leftRotate(node);
   if (balance > 1 && key > node->left->key) {
      node->left = leftRotate(node->left);
      return rightRotate(node);
   }
   if (balance < -1 && key < node->right->key) {
      node->right = rightRotate(node->right);
      return leftRotate(node);
   }
   return node;
}
void constructLowerArray(int arr[],
int countSmaller[],
int n){
   int i, j;
   struct node* root = NULL;
   for (i = 0; i < n; i++)
      countSmaller[i] = 0;
   for (i = n - 1; i >= 0; i--) {
      root = insert(root, arr[i], &countSmaller[i]);
   }
}
int countElements(int A[], int n, int K){
   int count = 0;
   int* countSmaller = (int*)malloc(sizeof(int) * n);
   constructLowerArray(A, countSmaller, n);
   int maxi = INT_MIN;
   for (int i = 0; i <= (n - K - 1); i++) {
      if (A[i] > maxi && countSmaller[i] >= K) {
         count++;
         maxi = A[i];
      }
   }
   return count;
}
int main(){
   int A[] = { 16, 10, 2022, 1997, 7, 2001, 0 };
   int n = sizeof(A) / sizeof(int);
   int K = 3;
   cout << countElements(A, n, K);
   return 0;
}

Ausgabe

2

Fazit

Wir wissen also, wie man C++-Code schreibt, um die Anzahl der Array-Elemente zu zählen, die größer sind als alle Elemente links davon und mindestens K Elemente rechts davon.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Zählen der Anzahl der Array-Elemente, die größer als alle Elemente links davon sind und mindestens K Elemente rechts davon haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!