Минимальные вызовы метода subArrayLeftShift для сортировки массива (вопрос интервью)
Предположим, у вас есть метод subArrayLeftShift(a,i), который сдвигает влево подмассив a [i, ..., n-1], когда n - длина массива. Это означает, что элементы a [i + 1], ..., a [n-1] перемещаются на одну позицию влево, а исходный a [i] станет последним.
Более формально вот реализация функции:
public static void subArrayLeftShift(int[] a, int i){
if (a.length == 0) return;
int last = a.length - 1;
int insertToLast = a[i];
for (; i < last; i++){
a[i] = a[i + 1];
}
a[last] = insertToLast;
}
Теперь вопрос: реализовать функцию, которая получает несортированный массив и возвращает минимальное количество вызовов subArrayLeftShift для сортировки массива.
В интервью я не нашел способа это сделать. Мне удалось найти минимальное количество вызовов для каждого примера, который я написал для интуиции, но не смог найти способа его обобщения.
Вы знаете, как это решить?
Похоже на вставку сортировки. Итак, я считаю, что максимальное количество звонков - это N, но минимум зависит от данных, это может быть даже 0,
Пожалуйста, не портите свои сообщения. Размещая в сети Stack Exchange, вы предоставляете SE безотзывное право распространять этот контент (в соответствии с Лицензия CC BY-SA 3.0). В соответствии с политикой SE любой вандализм будет пресечен.
Ответы 2
public static int minimumCalls(int[] a) {
int minCalls = 0;
for (int i = 0; i < a.length - 1; i++) {
for (int j = i+1; j < a.length; j++) {
if (a[i] > a[j]) {
minCalls++;
break;
}
}
}
return minCalls;
}
Идея, лежащая в основе моего мышления, заключается в том, что вы должны вызывать метод один раз, когда в SubArray существует какое-либо значение, меньшее, чем текущий i. Название метода subArrayShiftLeft, как мне кажется, создано для того, чтобы легко сбить вас с толку и отвлечь ваше внимание от размышлений об этом.
Если дальше в массиве есть какие-либо значения меньше текущего, просто вызовите метод.
Намного легче думать об этом как об перемещение одного большего значения в конец массива, чем о сдвинуть меньшие влево.
Ты прав. Я обнаружил это вскоре после публикации. Работаем над выяснением того, как обойти проблему.
Предлагаю следующий алгоритм решения проблемы:
- Найдите минимальное число в массиве, которое не отсортировано (имеет меньшее число справа в массиве). Пусть это число будет Икс.
- Подсчитайте, сколько чисел в массиве больше, чем ранее найденное число Икс. Пусть это число будет у.
Поскольку при каждом вызове функции неотсортированное число окажется на последней позиции, оптимальной стратегией является вызов функции для каждого неотсортированного числа в порядке возрастания. Используя то, что было найдено ранее, мы начинаем с Икс. Мы продолжаем со следующим неотсортированным числом больше x, потому что в этом случае оно окажется справа от Икс, следовательно, оно будет отсортировано. Продолжайте в том же духе. Как много? Насколько у нас число больше Икс? Ну это у. Таким образом, общее количество вызовов функции составляет 1 + г.
Не стыдно разместить свой код интуиция.