Минимальное количество соседних свопов для размещения похожих элементов вместе

Опубликовано: 16 Января, 2022

Дан массив из 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.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход : эту проблему можно решить с помощью жадного подхода. Ниже приведены шаги:

Сохраните массив посещенный [], который сообщает, что посещение [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>

Output:

Алгоритмы

Минимальное количество соседних свопов для размещения похожих элементов вместе

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ