Geek asks and answers

The minimum number of swaps?

The array has N characters in the strings of types A and B (the same amount of each type). What is the minimum number of swaps to make sure that two neighboring symbols are the same if we can only change two neighboring symbols? For example, input:

AAAABBBB

The minimum number of swaps is 6 to make an ABABABAB array. But how would you allow it for any input? I can only think of a solution O (N ^ 2). Maybe some kind of?

+3
source share
5 answers

If we just need to count the swaps , then we can do this with O (N) .

Suppose for simplicity that an array X of N elements should become ABAB ....

GetCount()
    swaps = 0, i = -1, j = -1
    for(k = 0; k < N; k++)
        if(k % 2 == 0)
            i = FindIndexOf(A, max(k, i))
            X[k] <-> X[i]
            swaps += i - k
        else
            j = FindIndexOf(B, max(k, j))
            X[k] <-> X[j]
            swaps += j - k
    return swaps

FindIndexOf(element, index)
    while(index < N)
        if(X[index] == element) return index
        index++
    return -1; // should never happen if count of As == count of Bs

, , , (, abBbbbA** --> abAbbbB**) O(1). , . i j A B , , FindIndexOf O(N).

, , O (N ^ 2).

. : AAAABBBB. B O (N) , A B..., B O (N), ABA B... .. , O (N ^ 2) .

+4

, - , , , . .

( , A) . AAAABBBB [0, 1, 2, 3], ABABABAB [0, 2, 4, 6].

, . ( ) A , .. , .

, , .

n = 2k A k.

ODDS = [1, 3, 5, ... 2k]


EVENS = [0, 2, 4, ... 2k - 1]

, , , min(abs(ODDS[0] - A[0]), abs(EVENS[0] - A[0])) swaps, .

EVENS ODDS, ( ) ,

define count_swaps(length, initial, goal)
  total = 0
  for i from 0 to length - 1
    total += abs(goal[i] - initial[i])
  end
  return total
end

define count_minimum_needed_swaps(k, A)
  return min(count_swaps(k, A, EVENS), count_swaps(k, A, ODDS))
end

, , count_minimum_needed_swaps, 2 * k = n; O(n) .

, count_minimum_needed_swaps, , .

+2

N, , .

#define N 4
char array[N + N];

for (size_t z = 0; z < N + N; z++)
{
    array[z] = 'B' - ((z & 1) == 0);
}

return 0;   // The number of swaps
0

@Nemo @AlexD . n ^ 2. @Nemo , , , , A B .

.

, A B, , A B . , WORD_N 2N, N As N Bs, A. ( 2N ).

, B A, , , WORD_{N-1}. , B A, , , , WORD_{N-1}.

B , , , , $N-1 $swaps, B A (, ), WORD_N = [A B WORD_{N-1}].

, N-1 , (WORD_1) . N-1 ,

N_swaps = (N-1) * N/2.

N - .

, WORD_{N-1}, , A. , , . , WORD_{N-1} A, , , ant, B, , WORD_{N-1}, , WORD_{N}, WORD_{N} 1 .

0

I think this answer is similar to phs answer, only in Haskell. The idea is that the resulting indexes for A(or B's) are known, so we just need to calculate how far from each initial index we need to move and sum the total.

Haskell Code:

Prelude Data.List> let is = elemIndices 'B' "AAAABBBB" 
                   in minimum 
                   $ map (sum . zipWith ((abs .) . (-)) is) [[1,3..],[0,2..]]
6 --output
-1
source

More articles:


All Articles