dsal 最小化给定数组之间相应索引处不等元素的数量

最小化给定数组之间相应索引处不等元素的数量

原文：https://www.geeksforgeeks.org/minimize-count-of-unequal-elements-at-corresponding-indices-between-given-arrays/

给定两个数组A[]和B[]，它们由N个正整数组成，和一个矩阵List[][]，由M对索引组成，任务是最大程度地减少不相等的相同索引元素的数量（A[i] != B[i]），通过在数组A[]中的任意一对给定索引之间交换。

示例：

输入：N = 5, M = 4, A[] = {1, 5, 9, 2, 3}, B[] = {2, 4, 5, 1, 3}, list[][] = {{1, 4}, {2, 3}, {3, 5}, {2, 5}}

输出：1

解释：

初始数组A[] = {1, 5, 9, 2, 3}。

在A[] = {2, 5, 9, 1, 3}中交换索引(1, 4)。

在A[] = {2, 9, 5, 1, 1, 3}中交换索引(2, 3)。

因此，在比较最终数组A[] = {2, 9, 5, 1, 3}与数组B[] = {2, 4, 5, 1, 3}，唯一不相等的相同索引元素对是A[2] != B[2]（基于 1 的索引）。

输入：N = 5, M = 4, A[] = {1, 10, 19, 6, 2}, B[] = {1, 6, 10, 2, 19}, list[][] = {{1, 4}, {2, 3}, {3, 5}, {2, 5}}

输出：2

方法：由于可以在对对列表中指定的数组A[]的元素进行任意次数的交换，因此可以将这些元素视为已连接的集合，并且在其内部交换允许的元素。以下是实现此方法的步骤：

遍历给定数组A[]并创建一组连通组件，可以使用不相交集轻松完成。
对于B[]中的每个元素，查找A[]中的相应元素（A[i], B[i]）是否属于同一连通组件与否。
如果是，则使A[i] = B[i]并继续。否则，增加不匹配对的数量。
完成上述所有步骤后，打印不匹配对的计数。

下面是上述方法的实现：

C++

// C++ program for the above approach 
#include <bits/stdc++.h>  
using namespace std;  

int find(int par[],int x); 
void unionn(int par[], int a, int b); 

// Function that count of the mismatched 
// pairs in bot the array 
int countPairs(int A[], int B[], int N, 
               int M, int List[][2]) 
{ 
    int count = 0; 

    // Create a parent array 
    // and initialize it 
    int par[N + 1]; 
    for(int i = 0; i <= N; i++) 
        par[i] = i; 

    // Preprocessing of the given 
    // pairs of indices 
    for(int i = 0; i < M; i++) 
    { 

        // 1-based indexing 
        int index1 = find(par, List[i][0] - 1); 
        int index2 = find(par, List[i][1] - 1); 

        // If both indices doesn't belong 
        // to same component 
        if (index1 != index2) 
        { 

            // Insert the indices in 
            // same component 
            unionn(par, index1, index2); 
        } 
    } 

    // Map to get the indices 
    // of array A 
    map<int, int> mp; 

    for(int i = 0; i < N; i++) 
    { 
        mp[A[i]] = i; 
    } 

    for(int i = 0; i < N; i++) 
    { 
        if (A[i] != B[i]) 
        { 

            // If current element is not 
            // present in array B then 
            // count this as mismatched 
            if(mp.find(B[i]) == mp.end()) 
            { 
                count++; 
                continue; 
            } 

            // Get the index of the element 
            // in array B 
            int j = mp[B[i]]; 

            // Check if both indices belong 
            // to same connected component 
            // if not increment the count 
            if (find(par, i) != find(par, j)) 
                count++; 
        } 
    } 

    // Return answer 
    return count; 
} 

// Function that gives the connected 
// component of each index 
int find(int par[],int x) 
{ 
    if (par[x] == x) 
        return x; 
    else
        return par[x] = find(par, par[x]); 
} 

// Function that creates the 
// connected componenets 
void unionn(int par[], int a, int b) 
{ 

    // Find parent of a and b 
    // recursively 
    a = find(par, a); 
    b = find(par, b); 

    if (a == b) 
        return; 

    // Update the parent of a 
    par[a] = b; 
}  

// Driver Code 
int main() 
{ 
    int N = 5; 
    int M = 4; 

    // Given arrays A[], B[] 
    int A[] = { 1, 5, 9, 2, 3 }; 
    int B[] = { 2, 4, 5, 1, 3 }; 

    // List of indices 
    int List[][2] = { { 1, 4 }, { 2, 3 }, 
                      { 3, 5 }, { 2, 5 } }; 

    // Function call 
    cout << countPairs(A, B, N, M, List); 

    return 0; 
}  

// This code is contributed by rutvik_56

Java

// Java program for the above approach 
import java.util.*; 

class GFG { 

    // Function that count of the mismatched 
    // pairs in bot the array 
    public static int countPairs(int A[], int B[], 
                                int N, int M, 
                                int[][] List) 
    { 
        int count = 0; 

        // Create a parent array 
        // and initialize it 
        int par[] = new int[N + 1]; 
        for (int i = 0; i <= N; i++) 
            par[i] = i; 

        // Preprocessing of the given 
        // pairs of indices 
        for (int i = 0; i < M; i++) { 

            // 1-based indexing 
            int index1 
                = find(par, List[i][0] - 1); 
            int index2 
                = find(par, List[i][1] - 1); 

            // If both indices doesn't belong 
            // to same component 
            if (index1 != index2) { 

                // Insert the indices in 
                // same component 
                union(par, index1, index2); 
            } 
        } 

        // HashMap to get the indices 
        // of array A 
        HashMap<Integer, Integer> map 
            = new HashMap<>(); 

        for (int i = 0; i < N; i++) { 
            map.put(A[i], i); 
        } 

        for (int i = 0; i < N; i++) { 
            if (A[i] != B[i]) { 

                // If current element is not 
                // present in array B then 
                // count this as mismatched 
                if (!map.containsKey(B[i])) { 
                    count++; 

                    continue; 
                } 

                // Get the index of the element 
                // in array B 
                int j = map.get(B[i]); 

                // Check if both indices belong 
                // to same connected component 
                // if not increment the count 
                if (find(par, i) != find(par, j)) 
                    count++; 
            } 
        } 

        // Return answer 
        return count; 
    } 

    // Function that gives the connected 
    // component of each index 
    public static int find(int par[], 
                        int x) 
    { 
        if (par[x] == x) 
            return x; 
        else
            return par[x] 
                = find(par, par[x]); 
    } 

    // Function that creates the 
    // connected componenets 
    public static void
    union(int par[], int a, int b) 
    { 
        // Find parent of a and b 
        // recursively 
        a = find(par, a); 
        b = find(par, b); 
        if (a == b) 
            return; 

        // Update the parent of a 
        par[a] = b; 
    } 

    // Driver Code 
    public static void
        main(String[] args) 
    { 
        int N = 5; 
        int M = 4; 

        // Given arrays A[], B[] 
        int A[] = { 1, 5, 9, 2, 3 }; 
        int B[] = { 2, 4, 5, 1, 3 }; 

        // List of indices 
        int List[][] 
            = { { 1, 4 }, { 2, 3 },  
                { 3, 5 }, { 2, 5 } }; 

        // Function Call 
        System.out.println( 
            countPairs(A, B, N, M, List)); 
    } 
}

Python3

# Python3 program for the above approach  

# Function that count of the mismatched 
# pairs in bot the array  
def countPairs(A, B, N, M, List): 

    count = 0

    # Create a parent array 
    # and initialize it 
    par = [0] * (N + 1) 
    for i in range(N + 1): 
        par[i] = i 

    # Preprocessing of the given 
    # pairs of indices 
    for i in range(M): 

        # 1-based indexing 
        index1 = find(par, List[i][0] - 1) 
        index2 = find(par, List[i][1] - 1) 

        # If both indices doesn't belong 
        # to same component 
        if(index1 != index2): 

            # Insert the indices in 
            # same component 
            union(par, index1, index2) 

    # HashMap to get the indices 
    # of array A 
    map = {} 

    for i in range(N): 
        map[A[i]] = i 

    for i in range(N): 
        if(A[i] != B[i]): 

            # If current element is not 
            # present in array B then 
            # count this as mismatched 
            if(B[i] not in map.keys()): 
                count += 1
                continue

            # Get the index of the element 
            # in array B 
            j = map[B[i]] 

            # Check if both indices belong 
            # to same connected component 
            # if not increment the count 
            if(find(par, i) != find(par, j)): 
                count += 1

    # Return answer 
    return count 

# Function that gives the connected 
# component of each index 
def find(par, x): 

    if(par[x] == x): 
        return x 
    else: 
        par[x] = find(par, par[x]) 
        return par[x] 

# Function that creates the 
# connected componenets 
def union(par, a, b): 

    # Find parent of a and b 
    # recursively 
    a = find(par, a) 
    b = find(par, b) 

    if(a == b): 
        return

    # Update the parent of a 
    par[a] = b 

# Driver Code 
N = 5
M = 4

# Given arrays A[], B[] 
A = [ 1, 5, 9, 2, 3 ] 
B = [ 2, 4, 5, 1, 3 ] 

# List of indices 
List = [ [ 1, 4 ], [ 2, 3 ], 
        [ 3, 5 ], [ 2, 5 ] ] 

# Function call 
print(countPairs(A, B, N, M, List)) 

# This code is contributed by Shivam Singh

C

// C# program for the above approach 
using System; 
using System.Collections.Generic; 
class GFG{ 

    // Function that count of the mismatched 
    // pairs in bot the array 
    public static int countPairs(int[] A, int[] B, int N, 
                                int M, int[, ] List) 
    { 
        int count = 0; 

        // Create a parent array 
        // and initialize it 
        int[] par = new int[N + 1]; 
        for (int i = 0; i <= N; i++) 
            par[i] = i; 

        // Preprocessing of the given 
        // pairs of indices 
        for (int i = 0; i < M; i++)  
        { 

            // 1-based indexing 
            int index1 = find(par, List[i, 0] - 1); 
            int index2 = find(par, List[i, 1] - 1); 

            // If both indices doesn't belong 
            // to same component 
            if (index1 != index2) 
            { 

                // Insert the indices in 
                // same component 
                union(par, index1, index2); 
            } 
        } 

        // Dictionary to get the indices 
        // of array A 
        Dictionary<int, int> map = new Dictionary<int, int>(); 
        for (int i = 0; i < N; i++)  
        { 
            if (map.ContainsKey(A[i])) 
                map[A[i]] = i; 
            else
                map.Add(A[i], i); 
        } 

        for (int i = 0; i < N; i++)  
        { 
            if (A[i] != B[i])  
            { 

                // If current element is not 
                // present in array B then 
                // count this as mismatched 
                if (!map.ContainsKey(B[i]))  
                { 
                    count++; 
                    continue; 
                } 

                // Get the index of the element 
                // in array B 
                int j = map[B[i]]; 

                // Check if both indices belong 
                // to same connected component 
                // if not increment the count 
                if (find(par, i) != find(par, j)) 
                    count++; 
            } 
        } 

        // Return answer 
        return count; 
    } 

    // Function that gives the connected 
    // component of each index 
    public static int find(int[] par, int x) 
    { 
        if (par[x] == x) 
            return x; 
        else
            return par[x] = find(par, par[x]); 
    } 

    // Function that creates the 
    // connected componenets 
    public static void union(int[] par, int a, int b) 
    { 
        // Find parent of a and b 
        // recursively 
        a = find(par, a); 
        b = find(par, b); 
        if (a == b) 
            return; 

        // Update the parent of a 
        par[a] = b; 
    } 

    // Driver Code 
    public static void Main(String[] args) 
    { 
        int N = 5; 
        int M = 4; 

        // Given arrays []A, []B 
        int[] A = {1, 5, 9, 2, 3}; 
        int[] B = {2, 4, 5, 1, 3}; 

        // List of indices 
        int[, ] List = {{1, 4}, {2, 3}, {3, 5}, {2, 5}}; 

        // Function Call 
        Console.WriteLine(countPairs(A, B, N, M, List)); 
    } 
} 

// This code is contributed by shikhasingrajput

输出：

时间复杂度：O(N + M)。

辅助空间：O(n)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/36608.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-02》

分类

最近更新

dsal 最小化给定数组之间相应索引处不等元素的数量

最小化给定数组之间相应索引处不等元素的数量

C++

Java

Python3

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-11-02》

dsal 最小化给定数组之间相应索引处不等元素的数量

最小化给定数组之间相应索引处不等元素的数量

C++

Java

Python3

C

留言

联系客服

dsal 查看更多书籍