Encuentre el número más grande y más pequeño en una array que contiene números pequeños y grandes

Dada una array arr[] de N números pequeños y/o grandes, la tarea es encontrar el número más grande y el más pequeño en esta array.

Ejemplos:

Entrada: N = 4, arr[] = {5677856, 657856745356587687698768, 67564, 45675645356576578564435647647}
Salida: Menor: 67564
Mayor: 45675645356576578564435644

Entrada: N = 5, arr[] = {56, 64, 765, 323, 4764}
Salida: Menor: 56
Mayor: 4764

Entrada: N = 3, arr[] = {56, 56, 56}
Salida: Menor: 56
Mayor: 56

Enfoque ingenuo: una manera fácil de resolver este problema es usar la clasificación basada en la comparación en todos los números, almacenados como strings. Si las strings comparadas tienen una longitud diferente , ordénelas primero en función de la longitud pequeña. Si las longitudes son iguales, use la función de comparación para encontrar el primer carácter no coincidente más grande y deduzca si pertenece a la primera o a la segunda string y clasifíquelos cuyo valor ASCII del primer carácter no coincidente sea más pequeño.

De esta forma obtendremos el vector final que tiene strings ordenadas cada vez más en función de su representación numérica. La primera string será la más pequeña y la última será la más grande.

Complejidad del tiempo: O(N*M*log N)

• O(N*log N) para ordenar la array
• O(M) para comparar dos números dígito por dígito cuando las longitudes son iguales

Espacio Auxiliar: O(1)

Enfoque eficiente: para resolver el problema de manera eficiente, siga la siguiente idea:

Este enfoque es similar a encontrar el número más grande y más pequeño en un vector numérico. La única diferencia es que también es necesario verificar la longitud de la string, ya que las strings con una longitud grande siempre formarán un número mayor que una con una longitud más pequeña.

Por ejemplo : «3452» con longitud 4 siempre será mayor que «345» con longitud 3. 
Similar es el caso de la string más pequeña.

Siga los pasos para resolver el problema:

• Inicialice minLen al número máximo posible y maxLen al número mínimo posible. Aquí minLen y maxLen representan la longitud del número más pequeño y el número más grande encontrado hasta ahora.
• Atraviese todas las strings una por una con i .
• Encuentre la longitud de la string actual como numLen .
• Si minLen > numLen asigne minLen a numLen y el número más pequeño como números[i] . De manera similar, si maxLen < numLen asigne maxLen a numLen y el número más grande como números [i] .
• Si minLen == numLen y maxLen == numLen , compare el número más pequeño y el número más grande encontrado hasta ahora con los números [i] . El número con el primer carácter no coincidente mayor será más grande y el otro será más pequeño.
• Devuelve el par del número más pequeño y más grande como la respuesta final.

A continuación se muestra la implementación del enfoque mencionado anteriormente:

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find biggest and
// smallest numbers
pair<string, string> findLargestAndSmallest(
  vector<string>& numbers)
{
    int N = numbers.size();
    int maxLen = 0, minLen = INT_MAX;
 
    // To store smallest and largest
    // element respectively
    pair<string, string> res;
 
    // Traverse each number in array
    for (int i = 0; i < N; i++) {
        int numLen = numbers[i].length();
 
        // Comparing current smallest
        // number with current number
 
        // If current number is smaller
        if (minLen > numLen) {
            minLen = numLen;
            res.first = numbers[i];
        }
 
        // If current number is of same length
        // Perform digitwise comparison
        else if (minLen == numLen)
            res.first
          = res.first.compare(numbers[i]) < 0
                            ? res.first
                            : numbers[i];
 
        // Comparing current largest
        // number with current number
 
        // If current number is larger
        if (maxLen < numLen) {
            maxLen = numLen;
            res.second = numbers[i];
        }
 
        // If current number is of same length
        // Perform digitwise comparison
        else if (maxLen == numLen)
            res.second
          = res.second.compare(numbers[i]) > 0
                             ? res.second
                             : numbers[i];
    }
 
    // Returning the result
    return res;
}
 
// Driver code
int main()
{
    vector<string> numbers
        = { "5677856", "657856745356587687698768", "67564",
            "45675645356576578564435647647" };
 
    // Calling the function
    pair<string, string> ans
        = findLargestAndSmallest(numbers);
 
    cout << "Smallest: " << ans.first;
    cout << endl;
    cout << "Largest: " << ans.second;
    return 0;
}

// Java code for the above approach
import java.io.*;
public class GFG {
  static String[] findLargestAndSmallest(String[] numbers)
  {
 
    int N = numbers.length;
    int maxLen = 0, minLen = Integer.MAX_VALUE;
    String[] res = { "", "" };
 
    // To store smallest and largest
    // element respectively
 
    // Traverse each number in array
    for (int i = 0; i < N; i++) {
      int numLen = numbers[i].length();
 
      // Comparing current smallest
      // number with current number
      // If current number is smaller
      if (minLen > numLen) {
        minLen = numLen;
        res[0] = numbers[i];
      }
 
      // If current number is of same length
      // Perform digitwise comparison
      else if (minLen == numLen)
        res[0] = ((res[0].length()
                   > numbers[i].length())
                  ? res[0]
                  : numbers[i]);
 
      // Comparing current largest
      // number with current number
 
      // If current number is larger
      if (maxLen < numLen) {
        maxLen = numLen;
        res[1] = numbers[i];
      }
 
      // If current number is of same length
      // Perform digitwise comparison
      else if (maxLen == numLen)
        res[1]
        = (res[1].length() > numbers[i].length()
           ? res[1]
           : numbers[i]);
    }
 
    // Returning the result
    return res;
  }
 
  // driver code
  public static void main(String[] args)
  {
    String[] numbers
      = { "5677856", "657856745356587687698768",
         "67564", "45675645356576578564435647647" };
    // Calling the function
    String[] ans = findLargestAndSmallest(numbers);
    System.out.println("Smallest: " + ans[0]);
    System.out.print("Largest: " + ans[1]);
  }
}
 
// This code is contributed by phasing17

# Python tcode for the above approach
INT_MAX = 2147483647
 
# Function to find biggest and
# smallest numbers
def findLargestAndSmallest(numbers):
    N = len(numbers)
    maxLen,minLen = 0,INT_MAX
 
    # To store smallest and largest
    # element respectively
    res = ["" for i in range(2)]
 
    # Traverse each number in array
    for i in range(N):
        numLen = len(numbers[i])
 
        # Comparing current smallest
        # number with current number
 
        # If current number is smaller
        if (minLen > numLen):
            minLen = numLen
            res[0] = numbers[i]
 
        # If current number is of same length
        # Perform digitwise comparison
        elif (minLen == numLen):
            res[0] = res[0] if (res[0] < numbers[i]) else numbers[i]
 
        # Comparing current largest
        # number with current number
 
        # If current number is larger
        if (maxLen < numLen):
            maxLen = numLen
            res[1] = numbers[i]
 
        # If current number is of same length
        # Perform digitwise comparison
        elif (maxLen == numLen):
            res[1] = res[1] if (res[1] > numbers[i]) else numbers[i]
 
    # Returning the result
    return res
 
# Driver code
numbers = ["5677856", "657856745356587687698768", "67564","45675645356576578564435647647"]
 
# Calling the function
ans = findLargestAndSmallest(numbers)
 
print(f"Smallest: {ans[0]}")
print(f"Largest: {ans[1]}")
 
# This code is contributed by shinjanpatra

// C# code for the above approach
 
using System;
 
public class GFG {
  static string[] findLargestAndSmallest(string[] numbers)
  {
 
    int N = numbers.Length;
    int maxLen = 0;
    int minLen = Int32.MaxValue;
    string[] res = { "", "" };
    // To store smallest and largest
    // element respectively
 
    // Traverse each number in array
    for (int i = 0; i < N; i++) {
      int numLen = numbers[i].Length;
      // Comparing current smallest
      // number with current number
      // If current number is smaller
      if (minLen > numLen) {
        minLen = numLen;
        res[0] = numbers[i];
      }
 
      // If current number is of same length
      // Perform digitwise comparison
      else if (minLen == numLen)
        res[0]
        = ((res[0].Length > numbers[i].Length)
           ? res[0]
           : numbers[i]);
 
      // Comparing current largest
      // number with current number
 
      // If current number is larger
      if (maxLen < numLen) {
        maxLen = numLen;
        res[1] = numbers[i];
      }
 
      // If current number is of same length
      // Perform digitwise comparison
      else if (maxLen == numLen)
        res[1] = (res[1].Length > numbers[i].Length
                  ? res[1]
                  : numbers[i]);
    }
 
    // Returning the result
    return res;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    String[] numbers
      = { "5677856", "657856745356587687698768",
         "67564", "45675645356576578564435647647" };
     
    // Calling the function
    String[] ans = findLargestAndSmallest(numbers);
    Console.WriteLine("Smallest: " + ans[0]);
    Console.WriteLine("Largest: " + ans[1]);
  }
}
 
// this code is contributed by phasing17

<script>
    // JavaScrip tcode for the above approach
    const INT_MAX = 2147483647;
 
    // Function to find biggest and
    // smallest numbers
    const findLargestAndSmallest = (numbers) => {
        let N = numbers.length;
        let maxLen = 0, minLen = INT_MAX;
 
        // To store smallest and largest
        // element respectively
        let res = new Array(2).fill("");
 
        // Traverse each number in array
        for (let i = 0; i < N; i++) {
            let numLen = numbers[i].length;
 
            // Comparing current smallest
            // number with current number
 
            // If current number is smaller
            if (minLen > numLen) {
                minLen = numLen;
                res[0] = numbers[i];
            }
 
            // If current number is of same length
            // Perform digitwise comparison
            else if (minLen == numLen)
                res[0]
                    = res[0] < numbers[i]
                        ? res[0]
                        : numbers[i];
 
            // Comparing current largest
            // number with current number
 
            // If current number is larger
            if (maxLen < numLen) {
                maxLen = numLen;
                res[1] = numbers[i];
            }
 
            // If current number is of same length
            // Perform digitwise comparison
            else if (maxLen == numLen)
                res[1]
                    = res[1] > numbers[i]
                        ? res[1]
                        : numbers[i];
        }
 
        // Returning the result
        return res;
    }
 
    // Driver code
    let numbers = ["5677856", "657856745356587687698768", "67564",
        "45675645356576578564435647647"];
 
    // Calling the function
    let ans = findLargestAndSmallest(numbers);
 
    document.write(`Smallest: ${ans[0]}<br/>`);
    document.write(`Largest: ${ans[1]}`);
 
// This code is contributed by rakeshsahni
 
</script>

Smallest: 67564
Largest: 45675645356576578564435647647

Complejidad de tiempo: O(N*M), donde N es el tamaño de la array y M es el tamaño del número más grande.

• O(N) para recorrer cada número de la array
• O(M) para comparar dos números dígito por dígito cuando las longitudes son iguales

Espacio Auxiliar: O(1)