¿Cómo obtener el número más grande y más pequeño en una array?

Dada una array arr[] de longitud N , la tarea es encontrar el número máximo y mínimo en la array.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: El máximo es: 5
El mínimo es: 1
Explicación: El máximo de la array es 5 
y el mínimo de la array es 1.

Entrada: arr[] = {5, 3, 7, 4, 2}
Salida: El máximo es: 7
El mínimo es: 2

Enfoque 1 (codicioso): el problema se puede resolver utilizando el enfoque codicioso :

La solución es comparar cada elemento de la array en busca de elementos mínimos y máximos considerando un solo elemento a la vez.

Siga los pasos para resolver el problema:

• Cree una variable mini/maxi e inicialícela con el valor en el índice cero de la array.
• Iterar sobre la array y comparar si el elemento actual es mayor que el maxi o menor que el mini .
• Actualice el elemento mini/maxi con el elemento actual para que el elemento mínimo/máximo se almacene en la variable mini/maxi.
• Devuelve la variable mini/maxi.

A continuación se muestra la implementación de la idea anterior:

// C++ code to implement the idea
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// and maxximum of the array
pair<int, int> findMinMax(int arr[], int n)
{
    int mini = arr[0];
    int maxi = arr[0];
 
    for (int i = 0; i < n; i++) {
        if (arr[i] < mini) {
            mini = arr[i];
        }
        else if (arr[i] > maxi) {
            maxi = arr[i];
        }
    }
    return { mini, maxi };
}
 
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    pair<int, int> ans = findMinMax(arr, N);
    cout << "Maximum is: " << ans.second << endl;
    cout << "Minimum is: " << ans.first;
    return 0;
}

// Java Code to implement the above idea
 
class GFG {
 
    // Function to find the minimum and maxximum of the
    // array
    static int[] findMinMax(int[] arr, int n)
    {
        int mini = arr[0];
        int maxi = arr[0];
 
        for (int i = 0; i < n; i++) {
            if (arr[i] < mini) {
                mini = arr[i];
            }
            else if (arr[i] > maxi) {
                maxi = arr[i];
            }
        }
        int[] ans = new int[2];
        ans[0] = mini;
        ans[1] = maxi;
        return ans;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5 };
          int N = arr.length;
 
        // Function call
        int[] ans = findMinMax(arr, N);
        System.out.print("Maximum is: " + ans[1]);
        System.out.print("\n"
                         + "Minimum is: " + ans[0]);
    }
}
 
// This code is contributed by lokesh(lokeshmvs21).

# python3 code to implement the idea
 
# Function to find the minimum
# and maxximum of the array
 
 
def findMinMax(arr, n):
 
    mini = arr[0]
    maxi = arr[0]
 
    for i in range(0, n):
        if (arr[i] < mini):
            mini = arr[i]
 
        elif (arr[i] > maxi):
            maxi = arr[i]
 
    return [mini, maxi]
 
 
if __name__ == "__main__":
 
    arr = [1, 2, 3, 4, 5]
    N = len(arr)
 
    # Function Call
    ans = findMinMax(arr, N)
    print(f"Maximum is: {ans[1]}")
    print(f"Minimum is: {ans[0]}")
 
    # This code is contributed by rakeshsahni

// C# Code to implement the above idea
using System;
 
public class GFG {
 
  // Function to find the minimum and maxximum of the
  // array
  static int[] findMinMax(int[] arr, int n)
  {
    int mini = arr[0];
    int maxi = arr[0];
 
    for (int i = 0; i < n; i++) {
      if (arr[i] < mini) {
        mini = arr[i];
      }
      else if (arr[i] > maxi) {
        maxi = arr[i];
      }
    }
    int[] ans = new int[2];
    ans[0] = mini;
    ans[1] = maxi;
    return ans;
  }
 
  public static void Main(String[] args)
  {
    int[] arr = { 1, 2, 3, 4, 5 };
    int N = arr.Length;
 
    // Function call
    int[] ans = findMinMax(arr, N);
    Console.Write("Maximum is: " + ans[1]);
    Console.Write("\n"
                  + "Minimum is: " + ans[0]);
  }
}
 
// This code is contributed by shikhasingrajput

Maximum is: 5
Minimum is: 1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque 2 (función de biblioteca): el problema se puede resolver utilizando las funciones de biblioteca proporcionadas en diferentes lenguajes de programación.

Podemos usar min_element() y max_element() para encontrar los elementos mínimo y máximo de la array en C++.

A continuación se muestra la implementación de la idea anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum value
int findMin(int arr[], int n)
{
    return *min_element(arr, arr + n);
}
 
// Function to find the maximum value
int findMax(int arr[], int n)
{
    return *max_element(arr, arr + n);
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << "Maximum is: " << findMax(arr, N) << endl;
    cout << "Minimum is: " << findMin(arr, N);
    return 0;
}

// Java Code to use the inbuilt Math functions
 
class GFG {
 
    static int findMin(int[] arr, int n)
    {
        int min = arr[0];
        for (int i = 1; i < n; i++) {
            min = Math.min(
                min,
                arr[i]); // Function to get minimum element
        }
        return min;
    }
 
    static int findMax(int[] arr, int n)
    {
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(
                max,
                arr[i]); // Function to get maximum element
        }
        return max;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int N = arr.length;
 
        // Function call
        System.out.print("Maximum is: " + findMax(arr, N));
        System.out.print("\n"
                         + "Minimum is: "
                         + findMin(arr, N));
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

// C# Code to use the inbuilt Math functions
 
using System;
 
public class GFG {
 
    static int findMin(int[] arr, int n)
    {
        int min = arr[0];
        for (int i = 1; i < n; i++) {
            min = Math.Min(
                min,
                arr[i]); // Function to get minimum element
        }
        return min;
    }
 
    static int findMax(int[] arr, int n)
    {
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            max = Math.Max(
                max,
                arr[i]); // Function to get maximum element
        }
        return max;
    }
 
    public static void Main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int N = arr.Length;
 
        // Function call
        Console.Write("Maximum is: " + findMax(arr, N));
        Console.Write("\n"
                         + "Minimum is: "
                         + findMin(arr, N));
    }
}
 
 
// This code contributed by shikhasingrajput

Maximum is: 5
Minimum is: 1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque 3 (comparaciones mínimas): para resolver el problema con un número mínimo de comparaciones, siga los pasos a continuación:

• Si N es impar, entonces inicialice mini y maxi como el primer elemento. 
• Si N es par, inicialice mini y maxi como mínimo y máximo de los dos primeros elementos respectivamente. 
• Para el resto de los elementos, selecciónelos en pares y compare
  • Máximo y mínimo con maxi y mini respectivamente. 

El número total de comparaciones será:

Si N es impar: 3*(N – 1)/2  
Si N es par: 1 Comparación inicial para inicializar min y max, y 3(N – 2)/2 comparaciones para el resto de elementos 
= 1 + 3*(N – 2) / 2 = 3N / 2 – 2

A continuación se muestra la implementación de la idea anterior:

// C++ code to implement the idea
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure is used to return
// two values from minMax()
struct Pair {
    int min;
    int max;
};
 
// Function to get the minimum and the maximum
struct Pair getMinAndMax(int arr[], int n)
{
    struct Pair minmax;
    int i;
 
    // If array has even number of elements
    // then initialize the first two elements
    // as minimum and maximum
    if (n % 2 == 0) {
        if (arr[0] > arr[1]) {
            minmax.max = arr[0];
            minmax.min = arr[1];
        }
        else {
            minmax.min = arr[0];
            minmax.max = arr[1];
        }
 
        // Set the starting index for loop
        i = 2;
    }
 
    // If array has odd number of elements
    // then initialize the first element as
    // minimum and maximum
    else {
        minmax.min = arr[0];
        minmax.max = arr[0];
 
        // Set the starting index for loop
        i = 1;
    }
 
    // In the while loop, pick elements in
    // pair and compare the pair with max
    // and min so far
    while (i < n - 1) {
        if (arr[i] > arr[i + 1]) {
            if (arr[i] > minmax.max)
                minmax.max = arr[i];
 
            if (arr[i + 1] < minmax.min)
                minmax.min = arr[i + 1];
        }
        else {
            if (arr[i + 1] > minmax.max)
                minmax.max = arr[i + 1];
 
            if (arr[i] < minmax.min)
                minmax.min = arr[i];
        }
 
        // Increment the index by 2 as
        // two elements are processed in loop
        i += 2;
    }
    return minmax;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    // Function call
    Pair minmax = getMinAndMax(arr, N);
 
    cout << "Maximum is: " << minmax.max << endl;
    cout << "Minimum is: " << minmax.min;
    return 0;
}

Maximum is: 5
Minimum is: 1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)