Минимальное количество соседних свопов для размещения похожих элементов вместе
Дан массив из 2 * N положительных целых чисел, где каждый элемент массива находится в диапазоне от 1 до N и встречается в массиве ровно дважды. Задача состоит в том, чтобы найти минимальное количество соседних свопов, необходимое для размещения всех одинаковых элементов массива вместе.
Примечание. Необязательно сортировать окончательный массив (после выполнения свопов).
Примеры:
Input: arr[] = { 1, 2, 3, 3, 1, 2 }
Output: 5
After first swapping, array will be arr[] = { 1, 2, 3, 1, 3, 2 },
after second arr[] = { 1, 2, 1, 3, 3, 2 }, after third arr[] = { 1, 1, 2, 3, 3, 2 },
after fourth arr[] = { 1, 1, 2, 3, 2, 3 }, after fifth arr[] = { 1, 1, 2, 2, 3, 3 }
Input: arr[] = { 1, 2, 1, 2 }
Output: 1
arr[2] can be swapped with arr[1] to get the required position.
Подход : эту проблему можно решить с помощью жадного подхода. Ниже приведены шаги:
- Сохраните массив посещенный [], который сообщает, что посещение [curr_ele] ложно, если операция подкачки не была выполнена для curr_ele.
- Пройдите через исходный массив и, если текущий элемент массива еще не был посещен, то есть посещен [arr [curr_ele]] = false , установите его в значение true и переберите другой цикл, начиная с текущей позиции до конца массива.
- Инициализируйте счетчик переменных, который будет определять количество перестановок, необходимых для размещения партнера текущего элемента в его правильной позиции.
- Во вложенном цикле счетчик увеличивается только в том случае, если посещенный [curr_ele] равен false (поскольку, если он истинен, это означает, что curr_ele уже был помещен в правильную позицию).
- Если партнер текущего элемента найден во вложенном цикле, прибавьте значение count к общему ответу.
Below is the implementation of above approach:
C++
// C++ Program to find the minimum number of // adjacent swaps to arrange similar items together #include <bits/stdc++.h> using namespace std; // Function to find minimum swaps int findMinimumAdjacentSwaps( int arr[], int N) { // visited array to check if value is seen already bool visited[N + 1]; int minimumSwaps = 0; memset (visited, false , sizeof (visited)); for ( int i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false ) { visited[arr[i]] = true ; // stores the number of swaps required to // find the correct position of current // element"s partner int count = 0; for ( int j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false ) count++; // If current element"s partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // Driver Code int main() { int arr[] = { 1, 2, 3, 3, 1, 2 }; int N = sizeof (arr) / sizeof (arr[0]); N /= 2; cout << findMinimumAdjacentSwaps(arr, N) << endl; return 0; } |
Java
// Java Program to find the minimum number of // adjacent swaps to arrange similar items together import java.util.*; class solution { // Function to find minimum swaps static int findMinimumAdjacentSwaps( int arr[], int N) { // visited array to check if value is seen already boolean [] visited = new boolean [N + 1 ]; int minimumSwaps = 0 ; Arrays.fill(visited, false ); for ( int i = 0 ; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false ) { visited[arr[i]] = true ; // stores the number of swaps required to // find the correct position of current // element"s partner int count = 0 ; for ( int j = i + 1 ; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false ) count++; // If current element"s partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // Driver Code public static void main(String args[]) { int arr[] = { 1 , 2 , 3 , 3 , 1 , 2 }; int N = arr.length; N /= 2 ; System.out.println(findMinimumAdjacentSwaps(arr, N)); } } // This code is contributed by // Sanjit_Prasad |
Python3
# Python3 Program to find the minimum number of # adjacent swaps to arrange similar items together # Function to find minimum swaps def findMinimumAdjacentSwaps(arr, N) : # visited array to check if value is seen already visited = [ False ] * (N + 1 ) minimumSwaps = 0 for i in range ( 2 * N) : # If the arr[i] is seen first time if (visited[arr[i]] = = False ) : visited[arr[i]] = True # stores the number of swaps required to # find the correct position of current # element"s partner count = 0 for j in range ( i + 1 , 2 * N) : # Increment count only if the current # element has not been visited yet (if is # visited, means it has already been placed # at its correct position) if (visited[arr[j]] = = False ) : count + = 1 # If current element"s partner is found elif (arr[i] = = arr[j]) : minimumSwaps + = count return minimumSwaps # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 3 , 1 , 2 ] N = len (arr) N / / = 2 print (findMinimumAdjacentSwaps(arr, N)) # This code is contributed by Ryuga |
C#
// C# Program to find the minimum // number of adjacent swaps to // arrange similar items together using System; class GFG { // Function to find minimum swaps static int findMinimumAdjacentSwaps( int []arr, int N) { // visited array to check // if value is seen already bool [] visited = new bool [N + 1]; int minimumSwaps = 0; for ( int i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false ) { visited[arr[i]] = true ; // stores the number of swaps required to // find the correct position of current // element"s partner int count = 0; for ( int j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false ) count++; // If current element"s partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // Driver Code public static void Main(String []args) { int []arr = { 1, 2, 3, 3, 1, 2 }; int N = arr.Length; N /= 2; Console.WriteLine(findMinimumAdjacentSwaps(arr, N)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript Program to find the minimum number of // adjacent swaps to arrange similar items together // Function to find minimum swaps function findMinimumAdjacentSwaps(arr, N) { // visited array to check if value is seen already let visited = Array(N + 1).fill( false ); let minimumSwaps = 0; for (let i = 0; i < 2 * N; i++) { // If the arr[i] is seen first time if (visited[arr[i]] == false ) { visited[arr[i]] = true ; // stores the number of swaps required to // find the correct position of current // element"s partner let count = 0; for (let j = i + 1; j < 2 * N; j++) { // Increment count only if the current // element has not been visited yet (if is // visited, means it has already been placed // at its correct position) if (visited[arr[j]] == false ) count++; // If current element"s partner is found else if (arr[i] == arr[j]) minimumSwaps += count; } } } return minimumSwaps; } // driver code let arr = [ 1, 2, 3, 3, 1, 2 ]; let N = arr.length; N = Math.floor(N / 2); document.write(findMinimumAdjacentSwaps(arr, N)); </script> |
5