По заданному индексу i, j (j & gt; = i) Как найти частоту A [j] в подрешетке (i, j)?
Учитывая массив A целых чисел, я пытаюсь выяснить в данной позиции j, сколько раз A [j] встречается от каждого i = 0 до i = j в A. Я разработал решение, подобное приведенному ниже.
map<int,int> CF[400005];
for(int i=0;i<n;++i)
{
cin>>A[i];
if(i!=0)
CF[i-1] = CF[i];
++CF[i][A[i]];
}
чем я могу ответить на каждый запрос во время входа в систему. Но эта процедура использует слишком много памяти. Есть ли способ сделать это, используя меньше памяти?
для большей ясности вы можете увидеть проблему, которую я пытаюсь решить http://codeforces.com/contest/190/problem/D
Решение
Создать массив B того же размера, что и A и карта C, Для каждого j в B[j] отслеживать количество случаев A[j] до j, В C отслеживать последнее вхождение данного элемента. Затем вы отвечаете на запросы в постоянное время, и это требует только O (n) памяти.
Извините за мой псевдо-C ++.
map<int,int> C;
int B[n]; // zeros
for(int i=0;i<n;++i)
{
cin >> A[i];
int prev = C[A[i]]; // let me assume it gives -1 if no element
if (pref == -1) // this is the fist occurrence of B[i]
B[i] = 1;
else // if not the first, then add previous occurrences
B[i] = B[prev] + 1
C[A[i]] = i; // keep track where the last info about A[j] is
}
Другие решения
Не слишком много времени, но, возможно, вместо использования карты будут все позиции, используйте список, в котором для каждого элемента вы ставите точки, в которых изменяется количество элементов, что-то вроде этого:
struct count_info
{
int index;
int count;
count_info* next;
};
...
std::map<int, count_info*> data;
, а затем найдите правильную позицию в этой очереди. Вам по-прежнему нужна одна карта, но под ней у вас будет только список этих указателей, и по запросу вы просматриваете A [i] на карте, а затем просматриваете список, пока i> index && следующий && я < next-> индекс. Конечно, если logn является обязательным, то это не удается, потому что поиск по списку в худшем случае n.