Второе по величине значение в массиве на C и C++
В этом уроке вы найдёте второе по величине различное значение массива за один проход, без сортировки.
Введение
Самый очевидный способ найти второе по величине значение - отсортировать массив, но это лишняя трата времени. На самом деле достаточно за один проход отслеживать два наибольших значения, пропуская значения, равные максимуму.
Главное
- Включите предупреждения компилятора (compiler warnings) и исправьте их все.
- Хорошо понимайте тип и время жизни (lifetime) каждого значения.
- Всегда проверяйте входные данные и границы индексов массивов.
Примеры кода на C и C++
#include <limits.h>
#include <stdio.h>
int main(void) {
int values[] = {7, 23, 12, 23, 9}, first = INT_MIN, second = INT_MIN;
// Maintain the two largest distinct values.
for (int i = 0; i < 5; ++i) { int value = values[i]; if (value > first) { second = first; first = value; } else if (value > second && value != first) second = value; }
printf("second=%d\n", second);
}
second=12#include <iostream>
#include <limits>
#include <vector>
int main() {
std::vector values{7, 23, 12, 23, 9}; int first = std::numeric_limits<int>::min(), second = first;
// Maintain the two largest distinct values.
for (int value : values) { if (value > first) { second = first; first = value; } else if (value > second && value != first) second = value; }
std::cout << "second=" << second << '\n';
}
second=12Сравнение C и C++
Переменные first и second начинаются с INT_MIN, наименьшего значения типа int. Когда значение больше first, прежнее значение first переходит в second. Когда значение находится между ними и не равно first, обновляется только second. Поэтому дважды встречающееся 23 не портит результат, и второе по величине значение 12.
C использует небольшие процедурные функции и открыто показывает, как данные представлены в памяти.
C++ по-прежнему позволяет работать на низком уровне, но добавляет библиотечные типы и более безопасные абстракции.
Упражнения для практики
Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.
- Проверьте неверный ввод и граничные значения.
- Скомпилируйте с флагами -Wall -Wextra -Wpedantic, чтобы включить больше предупреждений.
- Вынесите общие объявления в заголовочный файл, а реализацию в отдельный файл.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
Все задачи