Найти наибольшее и наименьшее число в массиве, содержащем как маленькие, так и большие числа

Опубликовано: 19 Сентября, 2022

Дан массив arr[] из N маленьких и/или больших чисел. Задача состоит в том, чтобы найти наибольшее и наименьшее число в этом массиве.

Примеры:

Input: N = 4, arr[] = {5677856, 657856745356587687698768, 67564, 45675645356576578564435647647}
Output: Smallest: 67564
Largest: 45675645356576578564435647647

Input: N = 5, arr[] = {56, 64, 765, 323, 4764}
Output: Smallest: 56
Largest: 4764

Input: N = 3, arr[] = {56, 56, 56}
Output: Smallest: 56
Largest: 56

Наивный подход. Одним из простых способов решения этой проблемы является использование сортировки на основе сравнения для всех чисел, хранящихся в виде строк. Если сравниваемые строки имеют разную длину, сначала отсортируйте их по малой длине. Если длины одинаковы, используйте функцию сравнения , чтобы найти первый самый большой несоответствующий символ и определить, принадлежит ли он первой или второй строке, и отсортировать их, чье значение ASCII первого несовпадающего символа меньше.

Таким образом, мы получим окончательный вектор, который имеет все более отсортированные строки на основе его числового представления. Первая строка будет самой маленькой, а последняя строка будет самой большой.

Временная сложность: O(N*M*log N)

  • O(N*log N) для сортировки массива
  • O(M) для сравнения двух чисел цифра за цифрой, когда их длины равны

Вспомогательное пространство: O(1)

Эффективный подход: для эффективного решения проблемы следуйте следующей идее:

This approach is similar to finding the biggest and smallest number in a numeral vector. The only difference is that there is need to check of the length of string as well since strings with big length will always form a bigger number than one with smaller length.

For Example: “3452” with length 4 will always be greater than “345” with length 3. 
Similar is the case for smallest string.

Следуйте инструкциям, чтобы решить проблему:

  • Инициализируйте minLen до максимально возможного числа и maxLen до минимально возможного числа. Здесь minLen и maxLen представляют длину наименьшего числа и наибольшего числа, найденных до сих пор.
  • Пройдите все строки одну за другой с помощью i .
  • Найдите длину текущей строки как numLen .
  • Если minLen > numLen назначьте minLen для numLen и наименьшее число как numbers[i] . Точно так же, если maxLen < numLen, присвойте maxLen numLen и самое большое число как numbers[i] .
  • Если minLen == numLen и maxLen == numLen, тогда сравните наименьшее число и наибольшее число, найденные до сих пор, с числами[i] . Число с первым большим несовпадающим символом будет больше, а другое меньше.
  • Верните пару наименьшего и наибольшего числа в качестве окончательного ответа.

Ниже приведена реализация вышеупомянутого подхода:

Временная сложность: O(N*M), где N — размер массива, а M — размер наибольшего числа.

  • O(N) для обхода каждого числа массива
  • O(M) для сравнения двух чисел цифра за цифрой, когда их длины равны

Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ