Kleinster Element in rotiertem sortiertem Vektor

Einführung

In diesem Lab werden wir ein C++-Programm erstellen, um das kleinste Element in einem rotierten sortierten Vektor zu finden. Ein sortierter Vektor kann an einem unbekannten Pivot-Element rotiert werden.

Skills Graph

Enthalte erforderliche Bibliotheken und deklariere Namensraum

Zunächst müssen wir die erforderlichen Bibliotheken einbinden und den Namensraum deklarieren. Dieser Code wird in der Datei ~/project/main.cpp geschrieben. Der vollständige Code für Schritt 1 ist unten angegeben:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

Erstelle eine Funktion, um das kleinste Element zu finden

Wir werden eine Funktion namens findMin erstellen, um das kleinste Element in dem rotierten sortierten Vektor zu finden. In dieser Funktion werden wir durch jedes Element des Vektors iterieren und überprüfen, ob dieses Element das kleinste Element ist. Die Logik zur Überprüfung, ob das Element das kleinste ist, wird in den Kommentaren im Codeblock erklärt. Der vollständige Code für Schritt 2 ist unten angegeben:

int findMin(vector<int> &m)
{
    int i;
    int n = m.size();
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            // Überprüfe das erste Element
            if (m[i] < m[n - 1] && m[i] < m[1])
                break;
        }
        else
        {
            // Überprüfe alle anderen Elemente
            if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
                break;
        }
    }
    return m[i % n];
}

Schreibe die Hauptfunktion, um den Code zu testen

In der Hauptfunktion werden wir einen Vektor namens v erstellen und ihn mit einigen Elementen initialisieren. Anschließend werden wir die findMin-Funktion aufrufen, um das kleinste Element im Vektor zu finden. Schließlich werden wir das kleinste Element ausgeben. Der vollständige Code für Schritt 3 ist unten angegeben:

int main()
{
    vector<int> v = {4, 5, 6, 7, 1, 3, 2};
    int n = v.size();
    int minimum = 0;
    cout << "The elements of the given vector are: ";
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    minimum = findMin(v);
    cout << "\n\nThe Minimum element in the given vector is: " << minimum << endl;
    return 0;
}

Kompilieren und Ausführen des Codes

Öffnen Sie ein Terminalfenster und navigieren Sie mit dem Befehl cd zum Verzeichnis, in dem die Datei main.cpp gespeichert ist. Kompilieren Sie dann den Code mit dem folgenden Befehl:

g++ main.cpp -o main

Wenn keine Fehler auftreten, führen Sie das ausführbare Programm mit dem folgenden Befehl aus:

./main

Sie sollten die folgende Ausgabe sehen:

The elements of the given vector are: 4 5 6 7 1 3 2
The Minimum element in the given vector is: 1

Diese Ausgabe bestätigt, dass unser Code das korrekte kleinste Element im Vektor gefunden hat.

Zusammenfassung

In diesem Lab haben wir ein C++-Programm erstellt, um das kleinste Element in einem rotierten sortierten Vektor zu finden. Wir haben dies erreicht, indem wir durch jedes Element im Vektor iteriert haben und überprüft haben, ob dieses Element das kleinste Element ist. Schließlich haben wir das kleinste Element in der Konsole ausgegeben. Wir hoffen, dass Ihnen dieses Lab bei Ihrem Lernprozess der Programmierung hilfreich war.