HackRank — Оптимизация поворота массива

Я работаю над базовым кодом поворота массива для задания на звание хакера. Код завершен и проходит все тестовые случаи, кроме двух, время ожидания которых истекает. Мне было интересно, есть ли способ сделать этот код более эффективным. Заранее спасибо.

class Result {

/*
 * Complete the 'rotLeft' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY a - List Array
 *  2. INTEGER d - Number of times to be retated
 */

public static List<Integer> rotLeft(List<Integer> a, int d) {
    // Write your code here
    int lowestVal;
    int size = a.size()-1;
    for (int x = 0; x < d; x++)
    {
        lowestVal = a.get(0);
        for (int i = 0; i < size; i++)
        {
            a.set(i, a.get(i+1));
        }
        a.set(size, lowestVal);
    }
    return a;
}

}

Вам не нужно делать это самостоятельно. Рассмотреть возможность

d %= a.size();
if (d == 0) {
    return a;
}

List<Integer> results = new ArrayList<>();
results.addAll(a.subList(d, a.size()));
results.addAll(a.subList(0, d));

return results;

Если d изначально 0, он будет вращаться с постоянным временем. Это то же самое, что и ваша функция.

Если d становится 0 (когда d кратно a.size()), он по-прежнему будет вращаться с постоянным временем. В то время как ваша функция будет вращаться d раз, чтобы вернуться к исходному списку.

Если d равно 1, каждый элемент списка будет скопирован один раз. Это то же самое, что и ваша функция.

Если d больше 1 и не делится без остатка на a.size(), это скопирует каждый элемент списка один раз. В то время как ваша функция будет копировать каждый элемент d раз. Так d * a.size() копии. Это особенно большое улучшение, когда d больше, чем a.size().

За кулисами он выполняет ту же работу, что и один из ваших for петли. Но вам не нужно управлять им вручную. И вам не нужно гнездиться с другим for петля.

Вам предстоит работать со списком или массивом? Они не совсем эквивалентны. Если данные представляют собой массив, вы, возможно, можете использовать в своем решении System.arrayCopy ().

Вам нужно повернуть на месте, или в результате может получиться новый массив (или список)?

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

Термин «массив списков» неуместен (обычно он означает массив списков).

То, что вы делаете, — это вращение влево (на расстояние 1) d раз, в то время как было бы более элегантно (и эффективно) повернуть влево (на расстояние d) только 1 раз. Кроме того, в процессе вы меняете свой ввод (параметр a). Это не всегда зло, но именно в вашем случае, поскольку отсутствие упоминания этого (в документации функции) заставляет вызывающих абонентов этого не ожидать.

Вот более приятная версия, использующая только вызовы высокого уровня:

public static List<Integer> rotLeft(List<Integer> a, int d) {
    d %= a.size();
    if (d < 0) d += a.size();
    List<Integer> newPrefix = a.subList(d, a.size());
    List<Integer> newPostfix = a.subList(0, d);
    List<Integer> result = new ArrayList<>(a.size());
    result.addAll(newPrefix);
    result.addAll(newPostfix);
    return result;
}

Если создание newPrefix и newPostfix кажется неэффективным: есть только представления, так что не беспокойтесь об этом.

PS: возвращение a сама (а не копия), если d==0 может показаться хорошей идеей, но не рекомендуется, если вы не полностью контролируете своих абонентов. Если есть внешние абоненты, они могут испортить ваш исходный список в любое время.