Массивы: Найдите минимальное количество свопов, чтобы сделать битничность массива минимальным?

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

bt_array[i] = 0, if i == 0;
            = bt_array[i-1] + 1, if a[i] > a[i-1]
            = bt_array[i-1] - 1, if a[i] < a[i-1]
            = bt_array[i-1], if a[i] == a[i-1]

bt = last item in bt_array

Мы говорим, что битничность массива минимальна, когда его битность равна 0, если она имеет нечетное число элементов или ее битности составляет +1 или -1, если она имеет четное число элементов.

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

Например, предположим, что a = {34,8,10,3,2,80,30,33,1}

Его начальный bt равен -2. Минимальное значение равно 0. Это может быть достигнуто только с одним обменом, а именно с заменой 2 и 3. Таким образом, выход должен быть равен 1.

Вот несколько тестовых примеров:

Тестовый случай 1: a = {34,8,10,3,2,80,30,33,1}, min swaps = 1 (swap 2 и 3)

Тестовый случай 2: {1,2,3,4,5,6,7}: min swaps = 2 (своп 7 с 4 и 6 с 5)

Тестовый случай 3: {10,3,15,7,9,11}: мин. swaps = 0. bt = 1 уже.

И еще несколько:

{2,5,7,9,5,7,1}: ток bt= 2. Обмен 5 и 7: minSwaps = 1

{1,7,8,9,10,13,11}: ток bt= 4: обмен 1,8: minSwaps = 1

{13,12,11,10,9,8,7,6,5,4,3,2,1}: ток bt= -12: своп (1,6), (2,5 ) и (3,4): minSwaps = 3

Мне задали этот вопрос в интервью, и вот что я придумал:

1. Sort the given array.
2. Reverse the array from n/2 to n-1.
3. Compare from the original array how many elements changed their position. 
   Return half of it.

И мой бит кода, который делает это:

int returnMinSwaps(int[] a){
    int[] a = {1,2,3,4,5,6,7};
    int[] b = a;
    Arrays.sort(b);
    for(int i=0; i<= b.length/2 - 1; i++){
        swap(b[b.length - i], b[b.length/2 - i]);
    }
    int minSwaps = 0;
    for(int i=0;i<b.length;i++){
        if(a[i] != b[i])
            minSwaps++;
    }
    return minSwaps/2;
}

К сожалению, я не получаю правильное минимальное количество способов для некоторых тестовых случаев, используя эту логику. Кроме того, я сортирую массив, который делает его в O(n log n), и это нужно сделать в O(n).

Ответы

Ответ 1

СРОЧНОЕ ОБНОВЛЕНИЕ: T3 не выполняется!

Рассмотрим α = [0, 7, 8, 3, 4, 10, 1, 6, 9, 2, 5]. Нет S ij (α), который может << → B (α) | более чем на 2.

Думая о поправках к методу...

Предупреждение

Это решение работает только тогда, когда нет равных элементов массива.

Не стесняйтесь предлагать обобщения, редактируя ответ.

Перейдите прямо к Заключение, если вы хотите пропустить скучную часть.

Введение

Определим оператор подкачки S ij по массиву a:

S ij (a): [... a i,... a j,...] → [... a j,... a i,...] ∀i, j ∈ [0; | a |) ∩ ℤ: я ≠ j

Давайте также относиться к битности как B (a) и более формально ее определять:

Очевидные факты:

  • Свопы симметричны:

    S ij (a) = S ji (a)

  • Два свопа независимы, если их целевые позиции не пересекаются:

    S ij (S kl (a)) = S kl (S ij ( a)) ∀i, j, k, l: {i, j} ∩ {k, l} = ∅

  • Два 2-зависимых свопа отменяют друг друга:

    S ij (S ij (a)) = a

  • Два однозависимых свопа сохраняют следующее:

    S jk (S ij (a)) = S ij (S ik ( a)) = S ik (S jk (a))

  • Разность битоничности всегда даже для массивов одинакового размера:

    (B (a) - B (a ')) mod 2 = 0 ∀a, a': | a | = | a '|

    Естественно, ∀i: 0 < я < | |

    B ([a i-1, a i]) - B ([a ' i-1, a ' i]) = sgn (a i - a i-1) - sgn (a' i - а '<суб > I-1суб > ),

    который может быть либо 1 - 1 = 0, либо 1 - -1 = 2, либо -1 - 1 = -2, либо -1 - -1 = 0, и любое число ± 2 `s и 0` Полученные результаты дают ровный результат.

    NB: это верно только в том случае, если все элементы в a отличаются друг от друга, то же самое с a!

Теоремы

[T1] | B (S ij (a)) - B (a) | ≤ 4 ∀a, S ij (a)

Без ограничения общности предположим, что:

  • 0 < i, j < | | - 1
  • j - я ≥ 2
  • a i-1 а <суб > + 1суб >
  • a j-1 а <суб > J + 1суб >

В зависимости от a i возможны 3 случая:

  • a i-1 a i a я + 1: sgn (a i - a i-1) + sgn (a я + 1 - a i) = 1 + 1 = 2
  • a i < a i-1 < a я + 1: sgn (a i - a i-1) + sgn (a я + 1 - a i) = -1 + 1 = 0
  • a i-1 a я + 1 a i: sgn (a i - a i-1) + sgn (a я + 1 - a i) = 1 + -1 = 0

При изменении a i и оставив все остальные элементы a неповрежденными, | B (a ') - B (a ) | ≤ 2 (где a ' - результирующий массив, для которого также применяются вышеприведенные 3 случая), так как никакие другие члены B (a) не изменили их значение, за исключением тех двух из 1-окрестности a i.

S ij (a) подразумевает, что описанное выше будет происходить дважды, один раз для a i и один раз для a j.

Таким образом, | B (S ij (a)) - B (a) | ≤ 2 + 2 = 4.

Аналогично, для каждого из углов и j - я = 1 макс. возможная дельта равна 2, что составляет ≤ 4.

Наконец, это прямо экстраполируется на a i-1 > a я + 1 и a j-1 > a j + 1.

КЭД

[T2] ∀a: | B (a) | ≥ 2 ∃S ij (a): | B (S ij (a)) | = | B (a) | - 2

{доказательство в процессе, нужно спать}

[T3] ∀a: | B (a) | ≥ 4 ∃S ij (a): | B (S ij (a)) | = | B (a) | - 4

{доказательство в процессе, нужно спать}

Заключение

От T1, T2 и T3 минимальное количество свопов, необходимых для минимизации | B (a) | равно:

⌊ | B (а) |/4⌋ + ß,

где ß равно 1, если | B (a) | mod 4 ≥ 2, 0 в противном случае.