0과 1의 목록을 분리하는 데 필요한 최소 인접 스왑 수는 얼마입니까?
1과 0의 그룹이 주어지면 모든 0이 함께 있고 모든 1이 함께 있도록 숫자를 그룹화한다는 데이터 구조 및 알고리즘 문제를 해결하려고합니다. 두 개의 인접한 요소 만 스왑 할 수있는 경우이를 수행하는 데 필요한 최소 스왑 수는 얼마입니까? 어떤 그룹이 끝에 있는지는 중요하지 않습니다.
예 :
[0,1,0,1] = [0,0,1,1] 1 개의 스왑
[1,1,1,1,0,1,0] = [1,1,1,1,1,0,0] 1 개의 스왑
[1, 0, 1, 0, 0, 0, 0, 1] = = [1,1,1,0,0,0,0,0] 6 개의 스왑
이것은 여기에서 묻는 질문과 다릅니다.
모든 0과 모든 1이 함께 있도록 필요한 최소 스왑 수를 찾습니다.
나는 배열을 정렬하지 않고 모든 0과 모든 1을 함께 그룹화하려고 노력하고 있으며 어느 쪽이 어느 쪽인지는 중요하지 않습니다.
어디서부터 시작해야할지 전혀 모르겠습니다. 누군가 나를 도울 수 있습니까?
답변
0에 초점을 맞 춥니 다. 각 스왑은 최종 주문에 더 가까운 단일 위치를 단일 0으로 이동합니다. 그런 다음 변위 0의 수와 변위의 심각도를 찾아 스왑의 수를 찾을 수 있습니다.
0이 배열의 시작 부분에 있다고 가정하여 시작하겠습니다. count_of_ones와 변위가 모두 0으로 초기화 된 두 가지를 추적합니다. 1을 찾을 때마다 count_of_ones가 증가합니다. 0을 찾을 때마다 변위를 count_of_ones만큼 증가시킵니다.
그런 다음 다른 방향으로이 작업을 수행합니다. 두 가지 모두 선형이므로 이것은 선형입니다.
예 : 1010001
1: count_of_ones: 0 -> 1
0: displacement: 0 -> 1
1: count_of_ones: 1 -> 2
0: displacement: 1 -> 3
0: displacement: 3 -> 5
0: displacement: 5 -> 7
1: count_of_ones: 2 -> 3
이 방향에 대한 답은 최종 변위 또는 7입니다. 반대로 5를 얻습니다. 최종 답은 5입니다.
사실, 최종 변위의 합 (모든 0으로 시작과 끝)은 항상 num_zeroes * num_ones와 같습니다. 이렇게하면 작업이 절반으로 줄어 듭니다 (여전히 선형이지만).
댓글에서 어떤 사람들은 내 대답을 이해하지 못한 것 같습니다. 여기에 더 명확하게하기위한 Ruby 구현이 있습니다.
def find_min_swaps(arr)
count_of_ones = 0
displacement = 0
arr.each do |v|
count_of_ones += 1 if v == 1
displacement += count_of_ones if v == 0
end
count_of_zeroes = arr.length - count_of_ones
reverse_displacement = count_of_ones * count_of_zeroes - displacement
return [displacement, reverse_displacement].min
end
0은 변위 <reverse_displacement (동일한 경우)이면 왼쪽에, 변위> reverse_displacement이면 오른쪽에 놓입니다.
하자 SUM0모두 0의 (0 기반) 인덱스의 합, 그리고하자 SUM1모든 사람들의 인덱스의 합계. 당신이 바꿀 때마다 10-> 01, SUM0하나 내려 가고, SUM1하나 올라갑니다. 그들은 당신이 스왑 할 때 반대 방향으로 이동합니다 01-> 10.
N00과 N11 이 있다고 가정 해 봅시다 . 배열의 시작 부분에 0이 함께 묶인 경우 SUM0 = N0*(N0-1)/2. 그것은 SUM0당신이 가질 수 있는 가장 작은 것입니다.
단일 인접 스왑은 SUM0정확히 1만큼 줄일 수 SUM0 - N0*(N0-1)/2있으므로 전면에 0을 함께 포장하려면 정확히 스왑 이 필요합니다 . 마찬가지로, SUM1 - N1*(N1-1)/2전면에서 함께 포장하려면 스왑 이 필요 합니다.
귀하의 대답은 다음 숫자 중 더 작은 것입니다. min( SUM0 - N0*(N0-1)/2 , SUM1 - N1*(N1-1)/2 )
이러한 값은 모두 선형 시간으로 계산하기 쉽습니다.
O (n 2 )를 사용하는 Bubble Sort를 사용하는 간단한 접근 방식 은 다음과 같습니다.
public class MainClass {
public static void main(String[] args) {
int[] arr = new int[]{1, 0, 0, 0, 0, 0, 0, 1, 0};
int minSwaps = minimumSwaps(arr);
System.out.println("Minimum swaps required: " + minSwaps);
}
public static int minimumSwaps(int[] array) {
int[] arr1 = array.clone(), arr2 = array.clone();
int swapsForRight = 0, swapsForLeft = 0;
boolean sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < arr1.length - 1; i++) {
if (arr1[i + 1] < arr1[i]) {
int temp = arr1[i + 1];
arr1[i + 1] = arr1[i];
arr1[i] = temp;
sorted = false;
swapsForRight++;
}
}
}
sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i > arr2.length - 1; i++) {
if (arr2[i + 1] < arr2[i]) {
int temp = arr2[i + 1];
arr2[i + 1] = arr2[i];
arr2[i] = temp;
sorted = false;
swapsForLeft++;
}
}
}
return swapsForLeft > swapsForRight ? swapsForRight : swapsForLeft;
}
}