Что влияет на скорость следующего кода Java? (Мошеннические уведомления о деятельности на HackerRank)

Question

Постановка проблемы:

Следующий код проходит тесты на корректность, но не соответствует временным рамкам выполнения.

В одном из советов говорилось, что я мог бы использовать очереди и счетную сортировку для решения следующей проблемы. Я научился делать сортировку, но не применил ее. Мне нужно понять , почему мне рекомендована очередь (я прочитал Java API, но я не понял, какие преимущества дает мне возможность извлекать или удалять только первый и последний элемент) в этой ситуации) и почему мой текущий код недостаточно эффективен (я сделал его довольно коротким, используя только один для -l oop)?

Еще одна вещь, как указано на официальной веб-странице API, Arrays.sort () использует Quicksort с двойным поворотом. Я читал, что этот тип сортировки имеет тенденцию быть быстрее, чем сортировка «Подсчет», тогда почему это рекомендуется?

Кроме того, какова временная сложность O (1).

static int activityNotifications(int[] expenditure, int d) {
        int numOfNotif = 0;
        //for each element starting from d up to the pre-last element
        // proceed to next element in the array
        for (int i = d; i < expenditure.length; i++) {
            //add the elements that are needed for calculating the median
            int[] trailingDays = Arrays.copyOfRange(expenditure, i - d, i);
            Arrays.sort(expenditure, i - d, i);
            //calculate the median
            double median;
            int index = (trailingDays.length - 1) / 2;
            if (trailingDays.length % 2 == 0) {
                median = (trailingDays[index] + trailingDays[index + 1]);
                median /= 2;
            } else
                median = trailingDays[index];
            //check if median violates the condition
            if (expenditure[i] >= 2 * median)
                numOfNotif++;
        }
        return numOfNotif;
    }

Answer 1

Я рекомендую внимательно взглянуть на определение сложности времени

Я сделал его довольно коротким, используя только одну форму -1 oop.

---

Хотя это единица для l oop, если массив содержит n элементов (или n дней), и нам нужно вычислить дни уведомлений о мошенничестве после первого d дней, нам нужно ввести для l oop n-d+1 раз.

И каждый раз, когда мы вводим для l oop, мы сначала копируем подмассив длины d, а затем выполняем сортировку по нему

копирование: O(d) по сложности времени

сортировка (при условии быстрой сортировки в среднем случае): O(d * log(d)) по временной сложности.

Таким образом, общая временная сложность для этого алгоритма составляет O(n * d * log(d)), если мы пренебрегаем меньшими членами.

---

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

Идея sliding window разумна: когда мы обрабатываем [20, 30, 40], мы можем использовать информацию, сгенерированную при обработке [10, 20, 30], вместо того, чтобы делать все заново.

Например, за исключением элементов 10 и 40, остальные элементы в двух шагах абсолютно одинаковы.

При наличии очереди первый элемент может представлять 10, а когда мы приступаем к процессу следующего раунда, мы просто убираем этот первый элемент и добавляем новый элемент.

Для нахождения медианы бега я предлагаю посмотреть шаблон с двумя кучами