Hackerrank "побив рекорд" решение


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

Самый простой способ для меня, чтобы повторить ввод для найти ответ, но я думаю, это бы означало, что за o(n) сложность, так что я думал решить проблему с помощью разделяй и властвуй подход надеясь, что это позволит уменьшить сложность решения.

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

private static int minScore, maxScore;

static int[] breakingRecords(int[] score) {
    int firstScore = score[0];
    int[] result = new int[2];
    minScore = maxScore = firstScore;
    count(score,1, score.length - 1, result);

    return result;
}

private static void count(int[] scores, int start, int end, int[] result) {
    if(start == end || end < start) {
        int score = scores[start];
        if(score > maxScore) {
            maxScore = score;
            result[0] = result[0] + 1;
        } else if(score < minScore) {
            minScore = score;
            result[1] = result[1] + 1;
        }
        return;
    }

    int partition = (end + start) / 2;

    count(scores, start, partition, result);
    count(scores,partition + 1, end, result);

}


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

Вы должны соответствовать ваш именования: int[] score и int[] scores.

Старайтесь не оставлять государство в static переменных. Либо передать государству явно в качестве параметров в функции-звонки, или использовать переменные экземпляра. Я рекомендую против мутирующие переменные экземпляра с рекурсией, поскольку вам придется думать о том, что стек вызовов выглядит, в то время как отслеживание того, что на изменчивы глобального состояния выглядит. Эти два стиля программирования просто не хорошо перемешать.

Вы кстати ни разу не проблема. Задача по сути своей О(Н), потому что вы должны учитывать все п входов. Кроме того, эта задача не может быть распараллелен. Вы должны рассматривать входы в последовательности, так что разделяй и властвуй-это не эффективная стратегия. В принципе, ваша Рекурсия-это просто бессмысленно сложный способ итерации по массиву от начала до конца.

Следующий простой цикл будет гораздо предпочтительнее:

public static int[] brokenRecords(int[] scores) {
int highScore = scores[0],
lowScore = scores[0],
highRecords = 0,
lowRecords = 0;
for (int i = 1; i < scores.length; i++) {
if (scores[i] > highScore) {
highScore = scores[i];
highRecords++;
}
if (scores[i] < lowScore) {
lowScore = scores[i];
lowRecords++;
}
}
return new int[] { highRecords, lowRecords };
}

3
ответ дан 1 марта 2018 в 01:03 Источник Поделиться