동일한 인접 값의 최소 수를 배열 shuffling

Question

안녕하세요, 알고리즘을 찾고 있어요, 같은 주어진 인접한 값의 최소 수가 될 수 있도록 입력으로 배열을 다시 셔플 것입니다.

내가 설명하려고합니다 :

in:[4,4,4,4,5,5,5,5] -> out: [4,5,4,5,4,5,4,5] or [5,4,5,4,5,4,5,4] 

in:[1,2,3,4,5,6,7,8] -> out: 모든 값이 더 인접한 값

in:[1,1,2,2,3,3,1,1] -> out: [1,2,1,3,1,2,3,1] 또는 othrt 조합을 다른

감사와 동일하기 때문에 할 것입니다 순서를!

Answer 1

max_cnt은 모든 요소 중에서 최대 발생 횟수이고 n은 배열 크기라고 가정합시다.

ceil(n/2) 개 이상의 요소가없는 경우 동일한 값을 가진 요소 사이의 거리가 2 이상이되도록 정렬 할 수 있으므로 인접한 요소를 모두 구분할 수 있습니다. 예 :
a = [1, 1, 1, 1, 2, 2, 3]. 우리는 그것을 다음과 같이 재정렬 할 수 있습니다 : [1, 2, 1, 2, 1, 3, 1]. 재배치를위한 알고리즘은 간단합니다 : i, i + 2, i + 4, ... 위치에 같은 원소를 넣는 것 등등.

위치가 max_cnt > ceil(n/2) 인 경우 위에서 설명한 알고리즘을 사용하여 인접 요소가 같지 않은 가능한 가장 긴 접두어를 구성한 다음 나머지 값으로 접미사를 채울 수 있습니다. 예 : a = [1, 1, 1, 1, 2, 3]. 접두사는 [1, 2, 1, 3, 1]입니다. 나머지는 나머지 것들로 채워진다 : [1, 2, 1, 3, 1, 1, 1]. 동등한 인접 요소의 수는 2 * max_cnt - n - 1입니다.