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


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

Вход : Арр[] = {1, 14, 2, 16, 10, 20}

Выход : 14

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

public static int findThirdLargest(int[] numbers) {
    if (numbers.length < 3) {
        throw new IllegalArgumentException("there should be at least three numbers");
    }

    int largest, secondLargest, thirdLargest;
    largest = secondLargest = thirdLargest = Integer.MIN_VALUE;

    for (int number : numbers) {

        if (number > largest) {
            thirdLargest = secondLargest;
            secondLargest = largest;
            largest = number;
        } else if (number > secondLargest) {
            thirdLargest = secondLargest;
            secondLargest = number;
        } else if (number > thirdLargest) {
            thirdLargest = number;
        }
    }

    return thirdLargest;
}


@Test
public void findThirdLargest() throws Exception {

    // with positive numbers
    Assert.assertEquals(1, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, 3}));
    Assert.assertEquals(2, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, 3, 4}));
    Assert.assertEquals(2, ThirdLargestNumber.findThirdLargest(new int[]{1, 4, 3, 2}));
    Assert.assertEquals(14, ThirdLargestNumber.findThirdLargest(new int[]{1, 14, 2, 16, 10, 20}));
    Assert.assertEquals(16, ThirdLargestNumber.findThirdLargest(new int[]{19, -10, 20, 14, 2, 16, 10}));

    // with negative numbers
    Assert.assertEquals(-100, ThirdLargestNumber.findThirdLargest(new int[]{-100, -2, -3}));
    Assert.assertEquals(-3, ThirdLargestNumber.findThirdLargest(new int[]{1, 2, -3, -1000}));
    Assert.assertEquals(-3000, ThirdLargestNumber.findThirdLargest(new int[]{-1000, -2000, -3000, -4000, -5000}));

    // what happens when all the numbers are same
    Assert.assertEquals(1, ThirdLargestNumber.findThirdLargest(new int[]{1, 1, 1, 1}));
}

Код: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/ThirdLargestNumber.java#5



Комментарии
1 ответ

Я думаю, что в целом он молодец, понятно и читаемо. Некоторые общие советы:


  • Вы можете принять параметр varargs, Что делает его проще назвать:

    public static int findThirdLargest(int... numbers)
    ...
    int thirdLargest = findThirdLargest(1, 2, 3);

  • Поскольку вы проверить размер массива, вы могли бы также проверить, если это не null.

  • Это несколько личное, но я бы всегда объявлять и инициализировать каждую переменную на отдельной строке, например:

    int largest = Integer.MIN_VALUE;
    int secondLargest = Integer.MIN_VALUE;
    int thirdLargest= Integer.MIN_VALUE;

Мне это помогает читабельности и потенциально рефакторинг позже.


  • Я удалить символ новой строки после for петли открывания. Это снижает читабельность для меня.

Приятно, что вы добавили тесты! Вы осветили некоторые хорошие дела. Вы могли бы взглянуть на Hamcrest первомайскую, вы можете создать некоторые хорошие декларативный тесты с ним. Они также могут показать вполне приличные сообщения в случае сбоя теста.

Некоторые дополнительные советы о текущих тестов:


  • Я бы разделил тесты в несколько различных методов

  • Лично мне нравится использовать статический импорт, поэтому можно написать:

    assertEquals(1, findThirdLargest(1, 2, 3))

  • Также не забудьте проверить, не случаях. Проверить, что когда вы проходите менее 3 цифр, вы ожидаете исключение.

А что должно на выходе findThirdLargest(1, 1, 2, 2, 3, 3) быть?

Наконец, последующие упражнения: как бы вы реализовать его, если пользователь хочет найти k-ый по величине элемент?

1
ответ дан 6 апреля 2018 в 07:04 Источник Поделиться