сопряженные целочисленные разбиения на месте

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

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

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, Напиши 0 позиционировать y и писать -y позиционировать x, На самом деле жизнь немного сложнее, чем это; если позиция x содержит положительное целое число, тогда нам нужно сохранить его во временном, а затем обработать его дальше. Наконец, просканируйте массив, заменив -x от x (очевидно, это не должен быть отдельный шаг). Таким образом, мы осуществляем перестановку, и у нас есть немного, чтобы запомнить, переместился ли конкретный элемент.

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

тогда мы устанавливаем out[] = [1,4,4,5,0](out[i]=in[i]);

мы сканируем out[] с конца, и найти первый ненулевой элемент, сохранить его как индекс 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по нашему предположению, это 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] бесполезен, и мы не теряем никакой информации.

если не соответствует предположению, мы можем добавить х к каждому элементу (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

Это [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();
}
}