Преобразование массива в отсортированный с использованием только двух операций
Я нашел этот вопрос на онлайн-форуме: действительно интересуется, как его можно решить:
Учитывая массив A положительных целых чисел. Преобразуйте его в отсортированный массив с минимальными затратами. Единственная действительная операция:
1) Снижение стоимости = 1
2) Удалите элемент из массива с помощью value = value элемента
Это вопрос интервью, заданный для технической компании
Ответы
Ответ 1
ПРИМЕЧАНИЕ. Первоначальный ответ был заменен на тот, в котором у меня гораздо больше уверенности (и я тоже могу это объяснить). Оба ответа дали одинаковые результаты в моем наборе тестовых случаев.
Вы можете решить эту проблему с помощью подхода динамического программирования. Главное наблюдение заключается в том, что никогда не имеет смысла уменьшать число до значения, не найденного в исходном массиве. (Неофициальное доказательство: предположим, что вы уменьшили число O1
до значения X
, которое не находится в исходной последовательности, чтобы избежать удаления числа O2 > X
из последовательности результатов. Затем вы можете уменьшить O1
до O2
и уменьшите стоимость на O2-X
).
Теперь решение становится понятным: это DP в двух измерениях. Если мы сортируем элементы отдельных элементов исходной последовательности d
в отсортированный массив s
, длина d
становится первым измерением DP; длина s
становится второй размерностью.
Объявляем dp[d.Length,s.Length]
. Значение dp[i,j]
- это стоимость решения подзадачи d[0 to i]
, сохраняя последний элемент решения при s[j]
. Примечание: эта стоимость включает стоимость устранения d[i]
, если она меньше s[j]
.
Первая строка dp[0,j]
вычисляется как стоимость обрезки d[0]
до s[j]
, или ноль, если d[0] < s[j]
. Значение dp[i,j]
следующей строки вычисляется как минимум dp[i-1, 0 to j] + trim
, где trim
- это стоимость обрезки d[i]
до s[j]
или d[i]
, если ее нужно устранить, поскольку s[j]
больше d[i]
.
Ответ вычисляется как минимум последней строки dp[d.Length-1, 0 to s.Length]
.
Вот реализация в С#:
static int Cost(int[] d) {
var s = d.Distinct().OrderBy(v => v).ToArray();
var dp = new int[d.Length,s.Length];
for (var j = 0 ; j != s.Length ; j++) {
dp[0, j] = Math.Max(d[0] - s[j], 0);
}
for (var i = 1; i != d.Length; i++) {
for (var j = 0 ; j != s.Length ; j++) {
dp[i, j] = int.MaxValue;
var trim = d[i] - s[j];
if (trim < 0) {
trim = d[i];
}
dp[i, j] = int.MaxValue;
for (var k = j ; k >= 0 ; k--) {
dp[i, j] = Math.Min(dp[i, j], dp[i - 1, k] + trim);
}
}
}
var best = int.MaxValue;
for (var j = 0 ; j != s.Length ; j++) {
best = Math.Min(best, dp[d.Length - 1, j]);
}
return best;
}
Эта прямая реализация имеет пространственную сложность O(N^2)
. Вы можете уменьшить его до O(N)
, заметив, что одновременно используются только две последние строки.
Ответ 2
Я предполагаю, что "сортировка" означает наименьшие значения в начале массива, учитывая характер разрешенных операций.
Граница производительности между двумя операциями возникает, когда стоимость удаления элемента из последовательности равна стоимости либо уменьшения всех более значимых элементов до и включая правонарушителя, либо удаления всех менее значимых элементов после преступник. Вы выбираете между декрементами предыдущих элементов или удалением более поздних элементов на основании того, почему элемент-нарушитель не соответствует последовательности. Если это меньше, чем предыдущий элемент, рассмотрите декремент предыдущих элементов; если он больше, чем следующий элемент, рассмотрим удаление более поздних элементов.
Некоторые примеры:
10 1 2 3 4 5
Уменьшение 10 к 1, стоимость 9.
1 2 3 4 10 4
Удалить 4, стоимость 4.
1 2 3 4 10 5
Удалите 5 или уменьшите 10 до 5, стоимость 5.
5 6 7 8 1 10
Удалить 1, стоимость 1.
5 6 7 8 6 10
Сокращение 7 и 8 до 6, стоимость 3.
2 1 1 4 2 4 4 3
Уменьшить первый 1, первый 4 на два и два других четыре раза один раз, стоимость 5.
Простейшая реализация для поиска решений основана на установлении знаний, поэтому она очень неэффективна. К счастью, на этот вопрос все равно. Идея состоит в том, чтобы пройти массив и принять решение о том, следует ли удалять или уменьшать, чтобы исправить набор, когда встречается элемент вне последовательности. Более эффективная реализация этого будет заключаться в использовании текущих итогов (в отличие от методов расчета) и перемещения массива дважды, вперед и назад. Я написал макет более простой версии, так как мне кажется, что ее легче читать.
Pseudocode, возвращает общую стоимость:
if array.Length < 2 : return 0; // no sorting necessary
resultArray = array.Copy();
int cost = 0;
for i = 0 to array.Length - 1 :
if i > 0 and array[i-1] > array[i] :
if CostToDecrementPreviousItems(i, array[i]) > array[i]) :
resultArray[i] = -1;
cost += array[i];
else :
cost += DecrementItemsThroughIndexGreaterThanValue(resultArray, i, array[i]);
end if
else if i < array.Length - 1 and array[i+1] < array[i] :
if CostToRemoveLaterItems(i, array[i]) > array[i] :
resultArray[i] = -1;
cost += array[i];
else :
cost += RemoveItemsAfterIndexGreaterThanValue(resultArray, i, array[i]);
end if
end if
end for
RemoveNegativeElements(resultArray);
array = resultArray;
return cost;
Надеемся, что вызовы метода undefined являются пояснительными.
Ответ 3
- Построить граф решений, добавить к нему стартовую вершину. Каждая вершина содержит "уровень обрезки", то есть значение, на которое должно быть уменьшено все значения массива слева от текущего node. Начало вершины "уровень обрезки" - бесконечность. Каждый край графика имеет значение, соответствующее стоимости решения.
- Для каждого элемента массива, начиная с самого правого, делайте шаги 3.. 5.
- Для каждой листовой вершины выполните шаги 4.. 5.
- Создайте до 2 исходящих ребер, (1) со стоимостью удаления элемента массива и (2) со стоимостью обрезки всех элементов влево (в точности, стоимость уменьшения "уровня отделки" ).
- Подключите эти ребра к вновь созданным вершинам, одну вершину для каждого элемента массива и каждый уровень обрезки.
- Найдите кратчайший путь от начальной вершины до одной из вершин, соответствующей самому крайнему элементу массива. Длина этого пути равна стоимости решения.
- Уменьшить и удалить элементы массива в соответствии с графиком принятия решений.
Этот алгоритм можно рассматривать как оптимизацию подхода грубой силы. Для поиска грубой силы, начиная с самого правого элемента массива, создайте двоичное дерево решений. Каждая вершина имеет 2 исходящих ребра, один для решения "удалить" , другое решение "trim". Стоимость решения связана с каждым ребром. "Уровень обрезки" связан с каждой вершиной. Оптимальное решение определяется кратчайшим путем в этом дереве.
Удалите все пути, что, очевидно, неоптимально. Например, если наибольший элемент является последним в массиве, решение "обрезать" имеет нулевое значение, а решение "удалить" является неоптимальным. Удалите путь, начиная с этого решения "удалить" . После этой оптимизации дерево решений более разреженное: некоторые вершины имеют 2 исходящих ребра, некоторые - только один.
На каждом уровне глубины дерево решений может иметь несколько вершин с одинаковым уровнем обрезки. Подэлементы, начиная с этих вершин, идентичны друг другу. Это хорошая причина для присоединения всех этих вершин к одной вершине. Это преобразует дерево в граф, содержащий не более n 2/2 вершин.
Сложность
Простейшей реализацией этого алгоритма является O (n 3), потому что для каждой из O (n 2) вершин он вычисляет затраты на обрезку итеративно, в O (n).
Повторные расчеты затрат на обрезку не нужны, если имеется достаточно памяти для хранения всех результатов частичной подгонки. Для этого может потребоваться O (n 2) или даже O (n) пространство.
При такой оптимизации этот алгоритм O (n 2). Из-за простой структуры графика поиск кратчайшего пути имеет сложность O (n 2), а не O (n 2 * log (n)).
Реализация С++ 11 (как пространственная, так и временная сложность O (n 2)):
//g++ -std=c++0x
#include <iostream>
#include <vector>
#include <algorithm>
typedef unsigned val_t;
typedef unsigned long long acc_t; // to avoid overflows
typedef unsigned ind_t;
typedef std::vector<val_t> arr_t;
struct Node
{
acc_t trimCost;
acc_t cost;
ind_t link;
bool used;
Node()
: trimCost(0)
, used(false)
{}
};
class Matrix
{
std::vector<Node> m;
ind_t columns;
public:
Matrix(ind_t rows, ind_t cols)
: m(rows * cols)
, columns(cols)
{}
Node& operator () (ind_t row, ind_t column)
{
return m[columns * row + column];
}
};
void fillTrimCosts(const arr_t& array, const arr_t& levels, Matrix& matrix)
{
for (ind_t row = 0; row != array.size(); ++row)
{
for (ind_t column = 0; column != levels.size(); ++column)
{
Node& node = matrix(row + 1, column);
node.trimCost = matrix(row, column).trimCost;
if (array[row] > levels[column])
{
node.trimCost += array[row] - levels[column];
}
}
}
}
void updateNode(Node& node, acc_t cost, ind_t column)
{
if (!node.used || node.cost > cost)
{
node.cost = cost;
node.link = column;
}
}
acc_t transform(arr_t& array)
{
const ind_t size = array.size();
// Sorted array of trim levels
arr_t levels = array;
std::sort(levels.begin(), levels.end());
levels.erase(
std::unique(levels.begin(), levels.end()),
levels.end());
// Initialize matrix
Matrix matrix(size + 1, levels.size());
fillTrimCosts(array, levels, matrix);
Node& startNode = matrix(size, levels.size() - 1);
startNode.used = true;
startNode.cost = 0;
// For each array element, starting from the last one
for (ind_t row = size; row != 0; --row)
{
// Determine trim level for this array element
auto iter = std::lower_bound(levels.begin(), levels.end(), array[row - 1]);
const ind_t newLevel = iter - levels.begin();
// For each trim level
for (ind_t column = 0; column != levels.size(); ++column)
{
const Node& node = matrix(row, column);
if (!node.used)
continue;
// Determine cost of trimming to current array element level
const acc_t oldCost = node.trimCost;
const acc_t newCost = matrix(row, newLevel).trimCost;
const acc_t trimCost = (newCost > oldCost)? newCost - oldCost: 0;
// Nodes for "trim" and "delete" decisions
Node& trimNode = matrix(row - 1, newLevel);
Node& nextNode = matrix(row - 1, column);
if (trimCost)
{
// Decision needed, update both nodes
updateNode(trimNode, trimCost + node.cost, column);
updateNode(nextNode, array[row - 1] + node.cost, column);
trimNode.used = true;
}
else
{
// No decision needed, pass current state to the next row node
updateNode(nextNode, node.cost, column);
}
nextNode.used = true;
}
}
// Find optimal cost and starting trim level for it
acc_t bestCost = size * levels.size();
ind_t bestLevel = levels.size();
for (ind_t column = 0; column != levels.size(); ++column)
{
const Node& node = matrix(0, column);
if (node.used && node.cost < bestCost)
{
bestCost = node.cost;
bestLevel = column;
}
}
// Trace the path of minimum cost
for (ind_t row = 0; row != size; ++row)
{
const Node& node = matrix(row, bestLevel);
const ind_t next = node.link;
if (next == bestLevel && node.cost != matrix(row + 1, next).cost)
{
array[row] = 0;
}
else if (array[row] > levels[bestLevel])
{
array[row] = levels[bestLevel];
}
bestLevel = next;
}
return bestCost;
}
void printArray(const arr_t& array)
{
for (val_t val: array)
if (val)
std::cout << val << ' ';
else
std::cout << "* ";
std::cout << std::endl;
}
int main()
{
arr_t array({9,8,7,6,5,4,3,2,1});
printArray(array);
acc_t cost = transform(array);
printArray(array);
std::cout << "Cost=" << cost << std::endl;
return 0;
}