Максимальная продукта триплета в массиве за линейное время


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

Вход: [1, -4, 3, -6, 7, 0]

Вывод: 168

Я хотел бы услышать от того, как это может быть переработаны/улучшены.

На GitHub

public static int highestProduct(int[] numbers) {
    int largest, secondLargest, thirdLargest;
    int smallest, secondSmallest;

    largest = secondLargest = thirdLargest = Integer.MIN_VALUE;
    smallest = secondSmallest = Integer.MAX_VALUE;

    for (int number : numbers) {

        // logic to find the largest numbers
        if (number > largest) {
            thirdLargest = secondLargest;
            secondLargest = largest;
            largest = number;
        } else if (number > secondLargest) {
            thirdLargest = secondLargest;
            secondLargest = number;
        } else if (number > thirdLargest) {
            thirdLargest = number;
        }

        // logic to find the smallest numbers
        if (number < smallest) {
            secondSmallest = smallest;
            smallest = number;
        } else if (number < secondSmallest) {
            secondSmallest = number;
        }
    }

    return Math.max(largest * secondLargest * thirdLargest,
            largest * smallest * secondSmallest);
}





   @Rule
public ExpectedException thrown = ExpectedException.none();

@Test
public void invalidInput() {
    thrown.expect(InvalidArgumentException.class);
    HighestProductOfThree.highestProduct(new int[]{1, 2});
}

@Test
public void allPositiveNumbers() {
    Assert.assertEquals(30000, HighestProductOfThree.highestProduct(new int[]{1, 3, 2, 100, 100}));
    Assert.assertEquals(40, HighestProductOfThree.highestProduct(new int[]{1, 2, 4, 5}));
}


@Test
public void allNegativeNumbers() {
    Assert.assertEquals(-30, HighestProductOfThree.highestProduct(new int[]{-20, -10, -5, -3, -2}));
}

@Test
public void mixedNumbers() {
    Assert.assertEquals(300, HighestProductOfThree.highestProduct(new int[]{-10, -10, 1, 3, 2}));
    Assert.assertEquals(168, HighestProductOfThree.highestProduct(new int[]{1, -4, 3, -6, 7, 0}));
} 


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

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

Я не вижу, где вы бросаете исключение сделать первые тесты успешно. Я уверен, что в настоящее время тест не пройден. Этот тест также импортирует InvalidArgumentException от странный пакет, а не использовать стандартные IllegalArgumentException. Ты идешь от .Чистый фон?

Ваш код довольно длинный. Если вы предпочитаете ремонтопригодность и читаемость в течение нескольких наносекунд времени исполнения (сложность \$\mathcal o(п\зарегистрируйте N)\$), можно написать:

int[] nums = numbers.clone();
Arrays.sort(nums);

int n = nums.length;
return Math.max(
nums[n - 3] * nums[n - 2] * nums[n - 1],
nums[0] * nums[1] * nums[n - 1]);

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