首页 > 试题广场 >

最佳配对

[编程题]最佳配对

热度指数：3751 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个长度为N的整型数组A和B。如果Ai==Bj则认为（i，j）为最佳配对。所有的最佳配对在满足以下条件的情况下组成最佳配对集合：A和B中的各个元素最多在集合中出现一次。例如，A =「5， 10， 11，12， 14」，B = 「8， 9 ，11， 11， 5」，配对集合为「（0，4），（2，2），（2，3）」，因为在集合A中索引2出现了两次，所以上面的配对集合不是最佳配对集合。你的任务是修改B中的一个元素，使得最佳配对集合的元素最多。并输出最佳配对集合的数量。

输入描述:

输入第一行为一个数字N，表示数组A和B的长度。输入第2行和3行都是N个数字，分别表示数组A和B的元素

输出描述:

修改B中的一个元素，并打印最大的最佳配对集合数量。注意：必须修改B中的一个元素。

示例1

输入

4
1 2 3 4
1 2 3 3

输出

算法知识视频讲解

Java

一然

import java.util.Scanner;
import java.util.ArrayList;
public class Main{
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int n= sc.nextInt();
        int[] a=new int[n];
        int[] b =new int[10];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        for(int i=0;i<n;i++){
            b[i]=sc.nextInt();
        }

//排序
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[j]<a[i]){
                    int temp=a[j];
                    a[j]=a[i];
                    a[i]=temp;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(b[j]<b[i]){
                    int temp1=b[j];
                    b[j]=b[i];
                    b[i]=temp1;
                }
            }
        }
        ArrayList<Integer[]> list =new ArrayList<>();
        int i=0,j=0;

//按顺序匹配
        while(i<n && j<n){
            if(a[i]>b[j]){
                j++;
            }else if(a[i]<b[j]){
                i++;
            }else {
                i++;j++;
                list.add(new Integer[]{i,j});
            }
        }

//如果一开始全匹配，至少更改一个b元素，否则+1,
        if(list.size()==n){
            System.out.println(list.size()-1);
        }else
            System.out.println(list.size()+1);

    }
}

发表于 2020-06-05 17:18:48 回复(0)

Java

努力努力Myzz

hash表+双层暴力循环

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = Integer.valueOf(sc.nextLine());
            String[] strs1 = sc.nextLine().split(" ");
            String[] strs2 = sc.nextLine().split(" ");
            int[] num1 = new int[n];
            int[] num2 = new int[n];
            for(int i =0;i<n;i++){
                num1[i] = Integer.valueOf(strs1[i]);
                num2[i] = Integer.valueOf(strs2[i]);
            }
            int num = 0;
            int total = 0;
            Map<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<n;i++){
                for(int j =0;j<n;j++){
                    if(num1[i]==num2[j] && !map.containsKey(num1[i])){
                            num++;
                            map.put(num1[i],1);
                    }
                }
            }
            for(int i=0;i<n;i++){
                if(!map.containsKey(num1[i]) && num<n) {
                        num++;
                }
                if(map.containsKey(num1[i])){
                        total++;
                }
            }
            if(total==n)num--;
            System.out.println(num);
        }
    }
}

发表于 2020-06-04 10:44:53 回复(1)