Найти второе по величине число в массиве

Подход

Одновременно отслеживаем первое и второе наибольшее число при проходе по массиву. За один проход обновляем обе переменные, учитывая повторяющиеся значения. Используем Integer.MIN_VALUE для инициализации.

Решение

public class SecondLargestFinder {
    
    /**
     * Находит второе по величине число в массиве за один проход.
     * 
     * @param arr массив целых чисел
     * @return второе наибольшее число или null если невозможно найти
     */
    public static Integer findSecondLargest(int[] arr) {
        // Обработка граничных случаев
        if (arr == null || arr.length < 2) {
            return null;
        }
        
        int largest = Integer.MIN_VALUE;
        int secondLargest = Integer.MIN_VALUE;
        
        // Проходим по массиву один раз
        for (int num : arr) {
            if (num > largest) {
                // Новый максимум найден
                secondLargest = largest;
                largest = num;
            } else if (num > secondLargest && num != largest) {
                // Новое второе по величине
                // Важно: num != largest для пропуска дубликатов максимума
                secondLargest = num;
            }
        }
        
        // Проверяем, было ли найдено второе наибольшее
        return (secondLargest == Integer.MIN_VALUE) ? null : secondLargest;
    }
    
    public static void main(String[] args) {
        System.out.println("=== Примеры поиска второго наибольшего числа ===");
        
        // Пример 1: Из задания
        int[] arr1 = {12, 35, 1, 10, 34, 1};
        System.out.println("Массив: " + java.util.Arrays.toString(arr1));
        System.out.println("Второе наибольшее: " + findSecondLargest(arr1));
        
        // Пример 2: С повторением максимума
        int[] arr2 = {10, 5, 10};
        System.out.println("Массив: " + java.util.Arrays.toString(arr2));
        System.out.println("Второе наибольшее: " + findSecondLargest(arr2));
        
        // Пример 3: Все элементы одинаковые
        int[] arr3 = {7, 7, 7, 7};
        System.out.println("Массив: " + java.util.Arrays.toString(arr3));
        System.out.println("Второе наибольшее: " + findSecondLargest(arr3));
        
        // Пример 4: Два уникальных элемента
        int[] arr4 = {100, 50};
        System.out.println("Массив: " + java.util.Arrays.toString(arr4));
        System.out.println("Второе наибольшее: " + findSecondLargest(arr4));
        
        // Пример 5: Отрицательные числа
        int[] arr5 = {-1, -5, -3, -2};
        System.out.println("Массив: " + java.util.Arrays.toString(arr5));
        System.out.println("Второе наибольшее: " + findSecondLargest(arr5));
    }
}

Сложность

• Временная сложность: O(n), один проход по массиву
• Пространственная сложность: O(1), только две переменные

Примеры и тест-кейсы

1. Базовый: [12, 35, 1, 10, 34, 1] -> 34
2. С дубликатами: [10, 5, 10] -> 5
3. Одинаковые элементы: [7, 7, 7] -> null
4. Два элемента: [100, 50] -> 50
5. Отрицательные: [-1, -5, -3] -> -2

Edge cases и типичные ошибки

1. Массив с одним элементом: Возвращаем null (нет второго)
2. Пустой массив: Возвращаем null
3. Все элементы одинаковые: Возвращаем null
4. Дубликаты максимума: [10, 10, 5] -> должно вернуть 5
5. Отрицательные числа: Алгоритм работает корректно

Решение демонстрирует оптимальное O(n) время выполнения за один проход.