У нас есть отсортированный массив, и мы хотели бы увеличить значение одного индекса только на 1 единицу (массив [i] ++), чтобы результирующий массив все еще сортировался. Возможно ли это в O (1)? Хорошо использовать любую структуру данных в STL и С++.
В более конкретном случае, если массив инициализирован всеми значениями 0 и он всегда инкрементно строится только путем увеличения значения индекса на единицу, существует ли решение O (1)?
Я не полностью отработал это, но я думаю, что общая идея может помочь, по крайней мере, для целых чисел. За счет большего объема памяти вы можете поддерживать отдельную структуру данных, которая поддерживает конечный индекс для запуска повторяющихся значений (так как вы хотите поменять ваше добавочное значение на конечный индекс повторяющегося значения). Это связано с тем, что с повторяющимися значениями, которые вы запускаете в наихудшем случае O(n) runtime: допустим, у вас есть [0, 0, 0, 0], и вы увеличиваете значение в месте 0. Затем O(n) определить последнее местоположение (3).
Но скажем, что вы поддерживаете структуру данных, о которой я упоминал (карта будет работать, потому что она имеет поиск O(1)). В этом случае у вас будет что-то вроде этого:
0 -> 3
Итак, у вас есть пробег 0, который заканчивается в месте 3. Когда вы увеличиваете значение, скажем, в месте i, вы проверяете, превышает ли новое значение значение в i + 1. Если это не так, вы в порядке. Но если это так, вы посмотрите, есть ли запись для этого значения во вторичной структуре данных. Если нет, вы можете просто поменяться местами. Если есть запись, вы просматриваете конечный индекс и затем обмениваетесь значением в этом месте. Затем вы вносите необходимые изменения во вторичную структуру данных, чтобы отразить новое состояние массива.
Более подробный пример:
[0, 2, 3, 3, 3, 4, 4, 5, 5, 5, 7]
Вторичная структура данных:
3 -> 4
4 -> 6
5 -> 9
Скажем, вы увеличиваете значение в месте 2. Таким образом, вы увеличили 3 до 4. Теперь массив выглядит следующим образом:
[0, 2, 4, 3, 3, 4, 4, 5, 5, 5, 7]
Вы смотрите на следующий элемент, который 3. Затем вы просматриваете запись для этого элемента во вторичной структуре данных. Запись 4, что означает, что существует пробег 3, который заканчивается на 4. Это означает, что вы можете поменять значение из текущего местоположения со значением в индексе 4:
[0, 2, 3, 3, 4, 4, 4, 5, 5, 5, 7]
Теперь вам также потребуется обновить вторичную структуру данных. В частности, запуск 3 заканчивается на один индекс раньше, поэтому вам нужно уменьшить это значение:
3 -> 3
4 -> 6
5 -> 9
Еще одна проверка, которую вам нужно будет сделать, это проверить, повторяется ли значение. Вы можете проверить это, посмотрев i - 1 th и i + 1 th местоположения, чтобы узнать, совпадают ли они с данным значением. Если ни один из них не равен, вы можете удалить запись для этого значения с карты.
Опять же, это всего лишь общая идея. Мне придется закодировать его, чтобы узнать, работает ли он так, как я думал об этом.
Пожалуйста, не стесняйтесь дышать.
UPDATE
У меня есть реализация этого алгоритма здесь в JavaScript. Я использовал JavaScript, чтобы сделать это быстро. Кроме того, поскольку я закодировал его довольно быстро, его можно, вероятно, очистить. У меня есть комментарии, хотя. Я тоже не делаю ничего эзотерического, поэтому это должно быть легко переносимым на С++.
Существует по существу две части алгоритма: приращение и свопинг (если необходимо) и ведение бухгалтерского учета на карте, которая отслеживает наши конечные индексы для повторений повторяющихся значений.
Код содержит тестовую жгуту, которая начинается с массива нулей и увеличивает случайные местоположения. В конце каждой итерации есть тест, чтобы убедиться, что массив отсортирован.
var array = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
var endingIndices = {0: 9};
var increments = 10000;
for(var i = 0; i < increments; i++) {
var index = Math.floor(Math.random() * array.length);
var oldValue = array[index];
var newValue = ++array[index];
if(index == (array.length - 1)) {
//Incremented element is the last element.
//We don't need to swap, but we need to see if we modified a run (if one exists)
if(endingIndices[oldValue]) {
endingIndices[oldValue]--;
}
} else if(index >= 0) {
//Incremented element is not the last element; it is in the middle of
//the array, possibly even the first element
var nextIndexValue = array[index + 1];
if(newValue === nextIndexValue) {
//If the new value is the same as the next value, we don't need to swap anything. But
//we are doing some book-keeping later with the endingIndices map. That code requires
//the ending index (i.e., where we moved the incremented value to). Since we didn't
//move it anywhere, the endingIndex is simply the index of the incremented element.
endingIndex = index;
} else if(newValue > nextIndexValue) {
//If the new value is greater than the next value, we will have to swap it
var swapIndex = -1;
if(!endingIndices[nextIndexValue]) {
//If the next value doesn't have a run, then location we have to swap with
//is just the next index
swapIndex = index + 1;
} else {
//If the next value has a run, we get the swap index from the map
swapIndex = endingIndices[nextIndexValue];
}
array[index] = nextIndexValue;
array[swapIndex] = newValue;
endingIndex = swapIndex;
} else {
//If the next value is already greater, there is nothing we need to swap but we do
//need to do some book-keeping with the endingIndices map later, because it is
//possible that we modified a run (the value might be the same as the value that
//came before it). Since we don't have anything to swap, the endingIndex is
//effectively the index that we are incrementing.
endingIndex = index;
}
//Moving the new value to its new position may have created a new run, so we need to
//check for that. This will only happen if the new position is not at the end of
//the array, and the new value does not have an entry in the map, and the value
//at the position after the new position is the same as the new value
if(endingIndex < (array.length - 1) &&
!endingIndices[newValue] &&
array[endingIndex + 1] == newValue) {
endingIndices[newValue] = endingIndex + 1;
}
//We also need to check to see if the old value had an entry in the
//map because now that run has been shortened by one.
if(endingIndices[oldValue]) {
var newEndingIndex = --endingIndices[oldValue];
if(newEndingIndex == 0 ||
(newEndingIndex > 0 && array[newEndingIndex - 1] != oldValue)) {
//In this case we check to see if the old value only has one entry, in
//which case there is no run of values and so we will need to remove
//its entry from the map. This happens when the new ending-index for this
//value is the first location (0) or if the location before the new
//ending-index doesn't contain the old value.
delete endingIndices[oldValue];
}
}
}
//Make sure that the array is sorted
for(var j = 0; j < array.length - 1; j++) {
if(array[j] > array[j + 1]) {
throw "Array not sorted; Value at location " + j + "(" + array[j] + ") is greater than value at location " + (j + 1) + "(" + array[j + 1] + ")";
}
}
}
В более конкретном случае, если массив инициализирован всеми значениями 0 и он всегда инкрементно строится только путем увеличения значения индекса на единицу, существует ли решение O (1)?
Нет. Учитывая массив всех 0: [0, 0, 0, 0, 0]. Если вы увеличиваете первое значение, предоставляя [1, 0, 0, 0, 0], вам нужно будет сделать 4 свопа, чтобы убедиться, что он по-прежнему отсортирован.
Учитывая отсортированный массив без дубликатов, тогда ответ будет да. Но после первой операции (т.е. При первом приращении), у вас могут быть дубликаты. Чем больше приращений вы делаете, тем выше вероятность того, что у вас будут дубликаты, и, скорее всего, это займет O (n), чтобы отсортировать этот массив.
Если все, что у вас есть, это массив, невозможно гарантировать меньше O (n) времени на шаг. Если вы ищете структуру данных, которая поддерживает отсортированный порядок и поиск по индексу, то вы, вероятно, захотите заказывать статическое дерево.
Если значения малы, подсчет сортировки будет работать. Представьте массив [0,0,0,0] как {4}. Приращение любого нуля дает {3,1}: 3 нули и один. В общем случае, чтобы прирастить любое значение x, вычесть один из числа x и увеличить счетчик {x + 1}. Эффективность пространства равна O (N), хотя, где N является наивысшим значением.
Это зависит от того, сколько элементов может иметь одинаковое значение. Если большее количество элементов может иметь одинаковое значение, тогда невозможно иметь O (1) с обычными массивами.
Сделайте пример: предположим, массив [5] = 21, и вы хотите сделать массив [5] ++:
Приращение элемента:
array[5]++
(это O (1), потому что это массив).
Итак, теперь массив [5] = 22.
Проверьте следующий элемент (т.е. массив [6]):
Если массив [6] == 21, вы должны продолжать проверять новые элементы (т.е. массив [7] и т.д.), пока не найдете значение выше 21. В этот момент вы можете поменять значения. Этот поиск не является O (1), потому что потенциально вы должны сканировать весь массив.
Вместо этого, если элементы не могут иметь одинаковое значение, то у вас есть:
Приращение элемента:
array[5]++
(это O (1), потому что это массив).
Итак, теперь массив [5] = 22.
Следующий элемент не может быть 21 (поскольку два элемента не могут иметь одинаковое значение), поэтому он должен иметь значение > 21, и массив уже отсортирован.
Итак, вы берете отсортированный массив и хэш-таблицу. Вы переходите по массиву, чтобы определить "плоские" области, где элементы имеют одинаковое значение. Для каждой плоской области вам нужно выяснить три вещи: 1) где она начинается (индекс первого элемента) 2) что это значение 3) каково значение следующего элемента (следующий больше). Затем поместите этот кортеж в хэш-таблицу, где ключ будет значением элемента. Это предпосылка, и эта сложность не имеет большого значения.
Затем, когда вы увеличиваете некоторый элемент (индекс i), вы просматриваете таблицу для индекса следующего более крупного элемента (назовите его j) и замените i на i - 1. Затем 1) добавьте новую запись в хэш-таблицу 2) обновите существующую запись для нее предыдущее значение.
С совершенной хэш-таблицей (или ограниченным диапазоном возможных значений) она будет почти равна O (1). Недостаток: он не будет стабильным.
Вот какой код:
#include <iostream>
#include <unordered_map>
#include <vector>
struct Range {
int start, value, next;
};
void print_ht(std::unordered_map<int, Range>& ht)
{
for (auto i = ht.begin(); i != ht.end(); i++) {
Range& r = (*i).second;
std::cout << '(' << r.start << ", "<< r.value << ", "<< r.next << ") ";
}
std::cout << std::endl;
}
void increment_el(int i, std::vector<int>& array, std::unordered_map<int, Range>& ht)
{
int val = array[i];
array[i]++;
//Pick next bigger element
Range& r = ht[val];
//Do the swapping, so last element of that range will be first
std::swap(array[i], array[ht[r.next].start - 1]);
//Update hashtable
ht[r.next].start--;
}
int main(int argc, const char * argv[])
{
std::vector<int> array = {1, 1, 1, 2, 2, 3};
std::unordered_map<int, Range> ht;
int start = 0;
int value = array[0];
//Build indexing hashtable
for (int i = 0; i <= array.size(); i++) {
int cur_value = i < array.size() ? array[i] : -1;
if (cur_value > value || i == array.size()) {
ht[value] = {start, value, cur_value};
start = i;
value = cur_value;
}
}
print_ht(ht);
//Now let increment first element
increment_el(0, array, ht);
print_ht(ht);
increment_el(3, array, ht);
print_ht(ht);
for (auto i = array.begin(); i != array.end(); i++)
std::cout << *i << " ";
return 0;
}
Да и нет.
Да, если список содержит только уникальные целые числа, так как это означает, что вам нужно только проверить следующее значение. Нет ни в какой другой ситуации. Если значения не уникальны, приращение первого из N повторяющихся значений означает, что он должен переместить N позиций. Если значения являются плавающей точкой, у вас могут быть тысячи значений между x и x + 1
Важно четко понимать требования; самый простой способ - выразить проблему как ADT (абстрактный тип данных), перечисляя необходимые операции и сложности.
Вот что я думаю, что вы ищете: тип данных, который предоставляет следующие операции:
Construct(n): создайте новый объект размера n, все значения которого 0.
Value(i): вернуть значение в индекс i.
Increment(i): Увеличить значение в индексе i.
Least(): вернуть индекс элемента с наименьшим значением (или одним из таких элементов, если их несколько).
Next(i): верните индекс следующего элемента после элемента i в отсортированном обходе, начиная с Least(), так что обход вернет каждый элемент.
Помимо конструктора, мы хотим, чтобы каждая из вышеперечисленных операций имела сложность O(1). Мы также хотим, чтобы объект занимал пространство O(n).
В реализации используется список ковшей; каждый ковш имеет value и список элементов. Каждый элемент имеет индекс, указатель на ведро, в котором он входит. Наконец, у нас есть массив указателей на элементы. (В С++ я бы, вероятно, использовал итераторы, а не указатели, на другом языке я бы, вероятно, использовал навязчивые списки.) Инварианты заключаются в том, что ведро никогда не пусто, а ведра value строго монотонно возрастают.
Начнем с одного ведра со значением 0, имеющего список элементов n.
Value(i) реализуется путем возврата значения ведра элемента, на который ссылается итератор в элементе i массива. Least() - это индекс первого элемента в первом ковше. Next(i) - это индекс следующего элемента после ссылки на итератор в элементе i, если только этот итератор уже не указывает в конце списка, и в этом случае он является первым элементом в следующем ведре, если только ведро элемента - это последнее ведро, и в этом случае мы находимся в конце списка элементов.
Единственный представляющий интерес интерфейс - Increment(i), который выглядит следующим образом:
Если элемент i является единственным элементом в его ведре (т.е. в списке веток нет следующего элемента, а элемент i является первым элементом в списке ведер):
O(1), независимо от размера списка, потому что это просто свод указателя), а затем удалить следующий ковш.Если элемент i не является единственным элементом в его ведре, то:
i в следующий список ковша.i и вставьте его между этим ведром и следующим.Я думаю, что это возможно без использования хэш-таблицы. У меня есть реализация здесь:
#include <cstdio>
#include <vector>
#include <cassert>
// This code is a solution for http://stackoverflow.com/questions/19957753/maintain-a-sorted-array-in-o1
//
// """We have a sorted array and we would like to increase the value of one index by only 1 unit
// (array[i]++), such that the resulting array is still sorted. Is this possible in O(1)?"""
// The obvious implementation, which has O(n) worst case increment.
class LinearIncrementor
{
public:
LinearIncrementor(int numElems);
int valueAt(int index) const;
void incrementAt(int index);
private:
std::vector<int> m_values;
};
// Free list to store runs of same values
class RunList
{
public:
struct Run
{
int m_end; // end index of run, inclusive, or next object in free list
int m_value; // value at this run
};
RunList();
int allocateRun(int endIndex, int value);
void freeRun(int index);
Run& runAt(int index);
const Run& runAt(int index) const;
private:
std::vector<Run> m_runs;
int m_firstFree;
};
// More optimal implementation, which increments in O(1) time
class ConstantIncrementor
{
public:
ConstantIncrementor(int numElems);
int valueAt(int index) const;
void incrementAt(int index);
private:
std::vector<int> m_runIndices;
RunList m_runs;
};
LinearIncrementor::LinearIncrementor(int numElems)
: m_values(numElems, 0)
{
}
int LinearIncrementor::valueAt(int index) const
{
return m_values[index];
}
void LinearIncrementor::incrementAt(int index)
{
const int n = static_cast<int>(m_values.size());
const int value = m_values[index];
while (index+1 < n && value == m_values[index+1])
++index;
++m_values[index];
}
RunList::RunList() : m_firstFree(-1)
{
}
int RunList::allocateRun(int endIndex, int value)
{
int runIndex = -1;
if (m_firstFree == -1)
{
runIndex = static_cast<int>(m_runs.size());
m_runs.resize(runIndex + 1);
}
else
{
runIndex = m_firstFree;
m_firstFree = m_runs[runIndex].m_end;
}
Run& run = m_runs[runIndex];
run.m_end = endIndex;
run.m_value = value;
return runIndex;
}
void RunList::freeRun(int index)
{
m_runs[index].m_end = m_firstFree;
m_firstFree = index;
}
RunList::Run& RunList::runAt(int index)
{
return m_runs[index];
}
const RunList::Run& RunList::runAt(int index) const
{
return m_runs[index];
}
ConstantIncrementor::ConstantIncrementor(int numElems) : m_runIndices(numElems, 0)
{
const int runIndex = m_runs.allocateRun(numElems-1, 0);
assert(runIndex == 0);
}
int ConstantIncrementor::valueAt(int index) const
{
return m_runs.runAt(m_runIndices[index]).m_value;
}
void ConstantIncrementor::incrementAt(int index)
{
const int numElems = static_cast<int>(m_runIndices.size());
const int curRunIndex = m_runIndices[index];
RunList::Run& curRun = m_runs.runAt(curRunIndex);
index = curRun.m_end;
const bool freeCurRun = index == 0 || m_runIndices[index-1] != curRunIndex;
RunList::Run* runToMerge = NULL;
int runToMergeIndex = -1;
if (curRun.m_end+1 < numElems)
{
const int nextRunIndex = m_runIndices[curRun.m_end+1];
RunList::Run& nextRun = m_runs.runAt(nextRunIndex);
if (curRun.m_value+1 == nextRun.m_value)
{
runToMerge = &nextRun;
runToMergeIndex = nextRunIndex;
}
}
if (freeCurRun && !runToMerge) // then free and allocate at the same time
{
++curRun.m_value;
}
else
{
if (freeCurRun)
{
m_runs.freeRun(curRunIndex);
}
else
{
--curRun.m_end;
}
if (runToMerge)
{
m_runIndices[index] = runToMergeIndex;
}
else
{
m_runIndices[index] = m_runs.allocateRun(index, curRun.m_value+1);
}
}
}
int main(int argc, char* argv[])
{
const int numElems = 100;
const int numInc = 1000000;
LinearIncrementor linearInc(numElems);
ConstantIncrementor constInc(numElems);
srand(1);
for (int i = 0; i < numInc; ++i)
{
const int index = rand() % numElems;
linearInc.incrementAt(index);
constInc.incrementAt(index);
for (int j = 0; j < numElems; ++j)
{
if (linearInc.valueAt(j) != constInc.valueAt(j))
{
printf("Error: differing values at increment step %d, value at index %d\n", i, j);
}
}
}
return 0;
}
просто перебирайте массив из модифицированного элемента, пока не найдете нужное место, а затем поменяйте. Средняя сложность случая - O (N), где N - среднее количество дубликатов. Наихудший случай - O (n), где n - длина массива. Пока N не является большим и плохо масштабируется с n, вы в порядке и, вероятно, можете сделать вид O (1) для практических целей.
Если дубликаты являются нормой и/или масштабируются с n, то есть лучшие решения, см. другие ответы.