Сопряженные целые разделы на месте

Ответ 1

Это можно сделать в 3 линейных проходах:

• Определите минимальный размер вектора, который позволяет выполнять сопряжение без перекрытия.
• Обратный исходный раздел; поскольку выход, измененный по отношению к входу, допускает меньшее перекрытие и, следовательно, меньшее дополнительное пространство.
• Выполнить сопряжение путем вектора заполнения с соответствующими индексами, повторяющимися столько раз, сколько разница между смежными значениями в исходном разделе.

Вот реализация С++ 11 (см. также полная программа на Ideone).

void conjugate()
{
    size_t space = 0;
    for (size_t i = 0; i < _length; ++i)
        space = max(space, _parts[i] + i);
    ++space;

    _parts.resize(space);
    reverse(begin(_parts), end(_parts));

    auto it_out = begin(_parts);
    auto it_in = end(_parts) - _length;
    size_t prev = 0;

    for (; it_in < end(_parts); ++it_in)
    {
        it_out = fill_n(it_out, *it_in - prev, end(_parts) - it_in);
        prev = *it_in;
    }

    _length = it_out - begin(_parts);
    _parts.resize(_length);
}

Эта реализация в некотором смысле на месте. Это означает, что он использует один вектор и минимизирует дополнительное пространство, необходимое для сопряжения. В некоторых случаях (например, {4,1,1,1} или {4,3,2,1}) к вектору добавляется только один дополнительный элемент. В сложных случаях (например, {4,4,4,4}) размер вектора временно удваивается.

Можно использовать этот подход, не используя лишнее пространство. Так как "плохие" случаи, такие как {4,4,4,4}, очевидно, имеют очень низкую энтропию, мы могли бы сжать исходный раздел. Однако это усложнит код.

Сочетание RLE и дельта-кодирования делает этот алгоритм действительно на месте (что означает O (1) дополнительное пространство). Используйте положительные числа (или нулевой высокий бит) для кодирования различий между смежными значениями в исходном разделе (поскольку шаг сопряжения в любом случае требует только различий). Используйте отрицательные числа (или ненулевой высокий бит) для кодирования прогонов нуля (оставшиеся биты номера указывают, сколько нулей). Все это ограничивает значение дельта и нулевой счетчик на половину диапазона. Но в обоих случаях может быть не более одного значения, превышающего половину диапазона. Таким образом, мы могли бы просто приписать это негативное значение нулевым (и резервным пространством в векторе не более 2 таких нулей).

Ответ 2

В этом ответе описывается алгоритм, который, возможно, не на месте, из-за его использования знакового бита. Поскольку вы используете подписанный тип, я все равно опубликую его.

Каждый разбиение определяется его максимумами однозначно. Для вашего примера раздела

4 | x
3 | x x x x
2 | x x x x
1 | x x x x x
    - - - - -
    1 2 3 4 5

где я обозначил оси координатами, а не внутренним представлением разбиения и его транспонированием, максимальные значения (1, 4), (4, 3) и (5, 1).

Первым/последним шагом алгоритма является преобразование в и из представления, описывающего максимумы. В общем, у нас есть место только для одной координаты, поэтому мы должны использовать положение в векторе для описания другого. Прямое преобразование просто заменяет все, кроме последнего вхождения каждого числа на 0.

5 4 4 1   -> 5 0 4 1
4 3 3 3 1 -> 4 0 0 3 1
             - - - - -
             1 2 3 4 5

Оба преобразования вперед и назад легко реализуются.

Средний шаг - сделать транспонирование на этом альтернативном представлении. Сканирование через массив, поиск положительных целых чисел. Когда мы найдем один, скажем x в позиции y, напишите a 0 в положение y и напишите -y в положение x. На самом деле жизнь немного сложнее, чем это; если позиция x содержит положительное целое число, тогда нам нужно сохранить его во временном порядке, а затем обработать его дальше. Наконец, сканирование через массив, заменяющий -x на x (очевидно, это не обязательно должен быть отдельный шаг). Итак, мы выполняем перестановку и имеем немного, чтобы помнить, перемещен ли какой-то конкретный элемент.

Ответ 3

input array in[] = [1,4,4,5], предположим in[i]>=i+1 (если это не так, добавьте x к каждому элементу).

то положим out[] = [1,4,4,5,0] (out[i]=in[i]);

мы сканируем out[] с конца и найдем первый элемент none-zero, сохраним его как p, а p означает, мы проанализируем out[p].

Укажите количество элементов, и мы получим результат.

[1,4,4,5,0] , p = 3, cnt = 1 (parse out[3] = 5)
->
[1,4,4,5,1] , p = 2, cnt = 3 (parse 4)
->
[1,3,3,3,1] , p = 0, cnt = 3 (parse 1)     
->
[4,3,3,3,1] , p = -1, cnt = 4 (done)     

когда мы анализируем out[i] (то есть in[i]), мы будем присваивать next_parse_element ~last_element_assigned-1, по нашему предположению, it next_element_index + 1~last element assigned-1, но next_element_index + 1~last element assigned анализируется нашей программой и бесполезно.

Пример ([1,4,4,5]): при анализе 4 следующий элемент 1, поэтому мы должны вычислить out[1](next parse element) ~ out[3](last_assigned - 1). Но вы видите, что out[1] - out[3] бесполезен, и мы не теряем никакой информации.

Если это не соответствует предположению, мы можем добавить x к каждому элементу (in[i]+=x), чтобы соответствовать предположению (самое большее добавить размер in, еще O(n) пробел). Затем мы делаем это как вышеописанный метод и игнорируем элементы x в начале out[], и это реальный ответ для ввода.

add 1 to every element in int[]
4 | x x
3 | x x x x x
2 | x x x x x
1 | x x x x x x
    - - - - - -
    1 2 3 4 5 6

It [4,4,3,3,3,1], игнорировать первый элемент и это реальный ответ.

Сложность времени. Если in[] не сортируется, то это O(nlogn), или O(n).

Подробнее см. мой код:

import java.util.Arrays;


public class Conjugate {
    int[] part;
    public Conjugate(int[] array) {
        Arrays.sort(array);
        int max = 0;
        for (int i = 0; i < array.length; i++)
        {
            max = Math.max(max, array[i]);
        }
        part = new int[Math.max(max,array.length)];
        for (int i = 0;i < array.length; i++)
        {
            part[i] = array[i];
        }
        int cnt = 0, p = part.length - 1, next = 0;
        for (int i = array.length-1; i >= 0; i--)
        {
            for (int j = i; j>=0&&part[i]==part[j]; j--)
            {
                cnt ++;
                if (j - 1 < 0)
                    next = 0;
                else 
                    next = part[j-1];
                i=j;
            }
            for (int j = p; j >= next ; j--)
            {
                part[j] = cnt;
            }
            p = next - 1 ;
        }
    }
    void output()
    {
        for (int i = 0; i < part.length; i++)
        {
            System.out.print(part[i] + " ");
        }
    }
    public static void main(String[] args) {
        int[] a = {1,4,4,5};
        Conjugate con = new Conjugate(a);
        con.output();
    }
}