Finden Sie das kleinste und zweitkleinste Element in einem Array

Wir können das kleinste und zweitkleinste Element eines Integer-Arrays mit der Sprache c finden. Diese Frage ist auch wichtig und wird vom Interviewer in einem Interview gestellt.

Nehmen wir ein Beispiel, angenommen, es gibt ein Integer-Array iaData mit 5 Integern.

int iaData[5] ={3, 5, 123, 6, 1};
Hier ist die kleinste Zahl 1 und die zweitkleinste Zahl 3.



Eine einfache Möglichkeit, das kleinste und zweitkleinste Element zu finden, besteht darin, das Array zu sortieren in aufsteigender Reihenfolge und wählen Sie das erste und zweite Element aus. Sein erstes Element ist die kleinste Zahl und die zweite Zahl ist die zweitkleinste Zahl. Die zeitliche Komplexität dieser Lösung ist O(n log n).

// C program to find smallest and second smallest elements
#include <stdio.h>

#define SIZE_ARRAY(x) sizeof(x)/sizeof(x[0]); // Size of array


int main()
{
    int iaData[5] = {3,5,123,6,1};
    int ArraySize = SIZE_ARRAY(iaData);
    int iLoop1 =0, iLoop2 =0;

    for(iLoop1 = 0; iLoop1 < ArraySize; iLoop1++)
    {
        for(iLoop2 = iLoop1+1; iLoop2 < ArraySize ; iLoop2++)
        {
            if(iaData[iLoop1] > iaData[iLoop2])
            {
                iaData[iLoop1] ^= iaData[iLoop2];
                iaData[iLoop2] ^= iaData[iLoop1];
                iaData[iLoop1] ^= iaData[iLoop2];
            }
        }
    }

    // Sorted array
    printf("\n\nSorted Array: ");
    for(iLoop1 = 0; iLoop1 < ArraySize; iLoop1++)
        printf("%d ",iaData[iLoop1]);

    // First element of sorted array
    printf("\n\nSmallest element = %d\n",iaData[0]);

    //Second element of sorted array
    printf("\n\nSecond smallest element = %d\n\n\n",iaData[1]);

    return 0;
}

Ausgabe:

Die obige Methode ist nicht besser, da sie das Array zweimal scannt. Es gibt auch eine andere Möglichkeit, das kleinste und zweitkleinste Element in einem einzigen Scan des Arrays zu finden. Die zeitliche Komplexität dieser Lösung ist O(n).

Hier ist ein Algorithmus, um die beiden kleinsten und die zweitkleinste Zahl in einem Durchlauf zu finden.

Algorithmus zum Finden des kleinsten und zweitkleinsten Elements:

• Erzeugt zwei Variablen. In diesem Code habe ich iFirstSmallest und iSecondSmallest erstellt.
• Initialisieren Sie beide Variablen als INT_MAX
  iFirstSmallest =INT_MAX
  iSecondSmallest =INT_MAX
• Durchlaufen Sie alle Elemente und führen Sie die folgende Aufgabe aus
  1). Wenn das aktuelle Element kleiner als iFirstSmallest ist, aktualisieren Sie iFirstSmallest und iSecondSmallest.
  2). Andernfalls, wenn das aktuelle Element kleiner als iSecondSmallest ist, dann aktualisiere iSecondSmallest.

#include <stdio.h>
#include <limits.h> /* For INT_MAX */


#define SIZE_ARRAY(x) sizeof(x)/sizeof(x[0]); //Element in array

void FindTwoSmallestNumber(int *piListOfData, int numbElement)
{
    int iLoop1= 0;
    int iFirstSmallest = INT_MAX;
    int iSecondSmallest = INT_MAX;

    while(iLoop1 < numbElement)
    {
        if(piListOfData[iLoop1] < iFirstSmallest)
        {
            iSecondSmallest = iFirstSmallest;
            iFirstSmallest  = piListOfData[iLoop1];

        }
        else if((piListOfData[iLoop1] < iSecondSmallest) && (piListOfData[iLoop1] !=iFirstSmallest ))
        {
            iSecondSmallest = piListOfData[iLoop1];
        }
        iLoop1++;
    }

    printf("First Smallest Numbers = %d\nSecond Smallest Number = %d\n ",iFirstSmallest,iSecondSmallest);

}


int main()
{
    int iaData[5] = {3,5,123,6,1};
    int numbElement = SIZE_ARRAY(iaData);

    FindTwoSmallestNumber(iaData,numbElement);

    return 0;
}

Ausgabe:

Empfohlene Artikel für Sie:

• Wie erstelle ich ein dynamisches Array in C?
• 15 Häufige Fehler bei der Speicherzuweisung.
• Arithmetische Operation auf Pointer in C.
• Wie greife ich auf 2D-Arrays in C zu?
• Eine kurze Beschreibung des Zeigers in C.
• Dangling-, Void-, Null- und Wild-Zeiger
• Funktionszeiger in c, eine ausführliche Anleitung
• Wie verwende ich die Struktur des Funktionszeigers in der Sprache C?
• Speicherlayout in C.
• 100 eingebettete C-Interviewfragen.
• Python-Interviewfragen mit Antwort.
• Dateiverwaltung in C.
• Funktionszeiger in Struktur.
• void pointer in C, Eine Detaildiskussion.
• 100 c Interviewfragen, die Ihr Interviewer stellen könnte.
• Dateiverwaltung in C.
• C-Formatbezeichner.