首页 > 试题广场 >

最佳配对

[编程题]最佳配对
  • 热度指数：3747 时间限制：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

输出

4
算法知识视频讲解
添加回答
Python
我要上岸！！头像 我要上岸！！ 
n = int(input())
a = [int(n) for n in input().split()]
b = [int(n) for n in input().split()]
count = 0
for item in b:
    if item in a:
        count += 1
        a.remove(item)
if count == n:
    print(count-1)
else: print(count+1)

发表于 2019-07-29 16:41:18 回复(1)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> arr1(n,0),arr2(n,0);
    for(int i=0;i<n;i++)
        cin>>arr1[i];
    for(int i=0;i<n;i++)
        cin>>arr2[i];
    sort(arr1.begin(),arr1.end());
    sort(arr2.begin(),arr2.end());
    int i=0,j=0,ans=0;
    while(i<n&&j<n){
        if(arr1[i]==arr2[j]){
            i++;
            j++;
            ans++;
        }
        else if(arr1[i]<arr2[j])
            i++;
        else
            j++;
    }
    ans==n ? ans--:ans++;
    cout<<ans;
    return 0;
}

发表于 2019-10-12 14:44:23 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,res=0;
    cin>>n;
    vector<int>a(n),b(n),c(n,0);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i]==b[j])
            {
                res++;
                b[j]=0;
                break;
            }
        }
    }
    if(res==n)
        res--;
    else
        res++;
    cout<<res<<endl;
    return 0;
}

发表于 2019-08-22 19:20:56 回复(0)
Bostonpigeons头像 Bostonpigeons 
#include<iostream>
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int a[1005],b[1005];
int main()
{
    map<int,int> m;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        m[a[i]]=-1;
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
        if(m[b[i]]==-1){
            m[b[i]]=1;
        }
    }
    int num=0;
    for(map<int,int>::iterator it=m.begin();it!=m.end();it++){
        if(it->second==1){
            num++;
           // cout<<it->first<<endl;
        }
    }
    if(num==n){
        cout<<n-1<<endl;
    }
    else cout<<num+1<<endl;
    return 0;
}
注意 3 1 2 3 1 2 3 为2
编辑于 2019-06-30 18:02:56 回复(3)
绅蓝头像 绅蓝 
        #include <bits/stdc++.h>
        using namespace std;
        int main()
        {
            intN;
            scanf("%d",&N);
            vector A(N);
            vector B(N);
            int count=0;
            for(int i=0;i<N;i++)
                scanf("%d",&A[i]);
            for(int i=0;i<N;i++)
                scanf("%d",&B[i]);
            unordered_map> num_A;//A中元素出现的位置
            unordered_map> num_B;//B中元素出现的位置
            vector temp;//备用区
            for(inti=0;i<N;i++)
            {
                num_A[A[i]].push_back(i);
                num_B[B[i]].push_back(i);
            }
            for(int i=0;i<N;i++)
            {
                if(num_A[A[i]].size()==1)//先保证A的元素不重复
                {
                   if(num_B.find(A[i])!=num_B.end())
                    {
                        if(num_B[A[i]].size()==1)
                            count++;
                        else
                            temp.push_back(A[i]);//不满足条件的放在备用区
                    }
                    else
                    temp.push_back(A[i]);//不满足条件的放在备用区
                }
            }
            if(temp.size()==0)//都满足条件，但必须改一个B元素
                count--;
            else
                count+=2;//B中有重复的，其中一个正常匹配，另一个改成别的，所以这里是+2
            cout<<count<<endl;
        }
编辑于 2019-07-07 12:30:19 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,cnt=0;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(a[i]==b[j]){
                cnt++;
                b[j] = 0;
                break;
            }
    cout<<((cnt==n)?cnt-1:cnt+1)<<endl;
    return 0;
}

发表于 2019-12-03 01:42:39 回复(0)
Python
牛客758087690号头像 牛客758087690号
l=int(input())
a=list(map(int,input().split(" ")))
b=list(map(int,input().split(" ")))
result = []
result_num = 0
for x in a:
    if x in b:
        if x not in result:
            result.append(x)
            result_num+=1
if len(result) < l:
    for x in a:
        if x not in result:
            print(result_num + 1)
            break
        if x==a[-1]:
            print(result_num)
else:
    print(result_num-1)
编辑于 2021-03-26 20:16:27 回复(0)
Bacon2020头像 Bacon2020 
#Input two lists of numbers by given amount
length = int(input())
num_list = []
for n in range(2):
    h = [int(x) for x in input().split(" ")]
    num_list.append(h)
 
#The list stores matched numbers of 1st list
match_x = []
#The list stores the index of extra same matches for values in list1 in list2
extra_match_index_j =[]
 
#Iterate every value of list 1
i=0
while i<len(num_list[0]):
    j=0
    occur=0
    while j<len(num_list[1]):
        if num_list[0][i] == num_list[1][j]:
            #Increment occurrence by 1
            occur+=1 
            #Only record match for values in 1st list one time!
            if occur<=1:
                match_x.append(num_list[0][i])
            else: #Otherwise, record the index of extra matches of 2nd list
                extra_match_index_j.append(j)
        j+=1
    i+=1
 

#Change one walue inside 2nd list
#If all values between two lists are matched
if len(extra_match_index_j)==0:
    num_list[1].pop() #reomve the last value in list2
else: #Otherwise replace a value at one reocrded index of extra match of list2 by an unmatched value in list1
    k=0
    while k<len(num_list[0]):
        if num_list[0][k] not in match_x:
            num_list[1][extra_match_index_j[0]]=num_list[0][k]
            break
        k+=1

 
#Count the number of matches after changing one value in list2
c=0
for item1 in num_list[0]:
    for item2 in num_list[1]:
        if item1 == item2:
            c+=1
#Print the count
print(c)


编辑于 2020-09-16 15:56:23 回复(0)
牛客577805498号头像 牛客577805498号 
import java.util.HashMap;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int[] a = new int[length];
        int[] b = new int[length];
        for (int i = 0; i < length; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 0; i < length; i++) {
            b[i] = scanner.nextInt();
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (a[i] == b[j]) {
                    if (!map.containsKey(i) && !map.containsValue(j)) {
                        map.put(i, j);
                    }
                }
            }
        }
        if (map.size() == length) {
            System.out.println(map.size()-1);
        }else {
            System.out.println(map.size()+1);
        }

    }
}

发表于 2020-07-21 09:46:51 回复(0)
0.068头像 0.068
使用HashSet存放数组中相同元素
如果set.size()==A.length，结果为set.size()-1,
如果set.size()<A.length,判断 A数组中剩余元素是否有与set中不重复的元素，有的话结果为set.size()+1,否则结果为set.size(); 
import java.util.*;
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[n];
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i<n; i++){
            A[i] = sc.nextInt();
        }
        for(int j = 0; j<n; j++){
            B[j] = sc.nextInt();
        }
        for(int i = 0; i<n; i++){
            for(int j = 0; j<n; j++){
                if(B[j] == A[i]){
                    set.add(A[i]);
                }
            }
        }
        if(set.size()==A.length){
            System.out.println(set.size()-1);
            return;
        }
        boolean flag = false;
        for(int i = 0; i<n; i++){
            if(!set.contains(A[i])){
                flag = true;
                break;
            }
        }
        if(flag == false){
            System.out.println(set.size());
        }else{
            System.out.println(set.size()+1);
        }
    }
}


发表于 2020-07-14 21:15:12 回复(0)
Python
牛客124928456号头像 牛客124928456号 
n=int(input())
v=list(map(int,input().split()))
w=list(map(int,input().split()))
a=[]
for i in range(n):
    if v[i] in w and v[i] not in a:
        a.append(v[i])
if len(a)==n:
    print(n-1)
else:
    print(len(a)+1)

发表于 2020-06-09 12:17:49 回复(0)
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头像 努力努力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)
ac_q头像 ac_q 
我的 思路清晰
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
using namespace std;

int main()
{
	int x = 0;
	int y = 0;
	int n = 0;
	cin >>  n;
    vector<int> vv1 (n);
	vector<int> vv2 (n);
	for (int i = 0; i < n; i++)
    {
        cin >> vv1[i];
    }
    for(int i = 0; i < n; i++)
    {
        cin >> vv2[i];
    }
    int count = 0;
    set<int>  s(vv1.begin(),vv1.end());
    set<int> s1;
    for(auto e: vv2)
    {
        if(s.find(e) != s.end() && s1.find(e) == s1.end())
        {
            s1.insert(e);
        }
        if(s.find(e) != s.end() && s1.find(e) != s1.end())
        {
            count++;
        }
    }
    if(s.size() > s1.size() && count >= 1)
    {
        cout << s1.size() + 1 << endl;
    }
    else
    {
        cout << s1.size() - 1 << endl;
    }
}

发表于 2020-06-03 22:29:20 回复(0)
fulanda1头像 fulanda1 
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
 
int BestPair(vector<int>input1, vector<int>input2) {
    int count = 0;
    for (int i = 0; i < input1.size(); i++) {
        for (int j = 0; j < input2.size(); j++) {
            if (input1[i] == input2[j] && input1[i]!=-1 && input2[j] != -1) {
                count++;
                input1[i] = -1;
                input2[j] = -1;
            }
        }
    }
    vector<int>temp1;
    vector<int>temp2;
    for (int i = 0; i < input1.size(); i++) {
        if (input1[i] != -1) {
            temp1.push_back(input1[i]);
        }
        if (input2[i] != -1) {
            temp2.push_back(input2[i]);
        }
    }
    if (temp1.size() >= 1 && temp2.size() >= 1) {
        count++;
        return count;
    }
    if (temp1.size() <1 || temp2.size() < 1) {
        count--;
        return count;
    }
     
 
}
 
 
 
int main() {
    int n;
    cin >> n;
    int temp;
    int count1 = 0;
    int count2 = 0;
    vector<int>input1;
    vector<int>input2;
    while (1) {
        cin >> temp;
        input1.push_back(temp);
        count1++;
        if (count1 == n) {
            break;
         
        }
    }
    while (1) {
        cin >> temp;
        input2.push_back(temp);
        count2++;
        if (count2 == n) {
            break;
             
        }
    }
    int ll;
    cout << BestPair(input1, input2);
    return 0;
 
}


发表于 2019-11-17 18:41:37 回复(0)
瓜子儿。头像 瓜子儿。 
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BestPairing {
//思路---本题等价于A==B?A交B:A交B+1 A==B指A集合与B集合元素除下标外完全相等
//按照这个思路，排序O(nlogn)+遍历O(n)就能判断A==B的真值并能求出A交B的值
//优化--能不能不排序？利用Set先放入集合A再遍历B将已有元素置空，
则有A交B=(2n-set.size())/2 【set为空代表相等】
//有个问题，集合中可能会含有重复元素--可用hashmap，结构类似于->map(key,count)
	public static void main(String[] args) {
		Scanner read=new Scanner(System.in);
		int n=read.nextInt();
		int[] arrA=new int[n],arrB=new int[n];
		for(int i=0;i<n;i++)
			arrA[i]=read.nextInt();
		for(int i=0;i<n;i++)
			arrB[i]=read.nextInt();
		read.close();
//		sortWay(arrA,arrB);
		mapWay(arrA,arrB);
	}
	
	public static void sortWay(int[] arrA,int[] arrB) {
		int n=arrA.length;
		Arrays.sort(arrA);
		Arrays.sort(arrB);
		int intersect=0,a=0,b=0;
		while(a<n&&b<n) {
			if(arrA[a]==arrB[b]) {
				++intersect;
				++a;
				++b;
			}else if(arrA[a]>arrB[b])
				++b;
			else ++a;
		}
		if(intersect==n)
			--intersect;
		else ++intersect;
		System.out.println(intersect);
	}
	public static void mapWay(int[] arrA,int[] arrB) {
		Map<Integer,Integer> map=new HashMap<>();
		for(int i : arrA)
			if(map.containsKey(i))
				map.put(i,map.get(i)+1);
			else
				map.put(i, 1);
		for(int i : arrB) 
			if(map.containsKey(i)) {
				int val=map.get(i);
				if(val==1)
					map.remove(i);
				else
					map.put(i, val-1);
			}else
				map.put(i, -1);
		if(map.isEmpty())
			System.out.println(arrA.length-1);
		else {
			int intersect=0;
			for(int i : map.keySet())
				intersect+=Math.abs(map.get(i));
			intersect=(2*arrA.length-intersect)/2;
			System.out.println(intersect+1);
		}
	}
}


编辑于 2019-10-27 21:00:42 回复(0)
offer加油头像 offer加油
这道题的测试用例太简单了。。情况还是比较多的，感觉大家的答案考虑的都有问题
考虑一下几种情况：
1.     A中有未匹配的元素，因此B中可以修改增加一个匹配
       1 2 3  和 1 2 4           1 1 2 2 3 和 1 1 2 2 4
2.    A中无重复元素，且全部匹配完成，则无论B改了什么都会-1
       1 2 3  和 1 2 3
3.    A中有重复元素，且全部匹配完成，则不会减少（因为A、B数组大小是一致的）
      1 3 3  和 1 3 3

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,tmp,count=0;
    cin>>n;
    unordered_map<int,int> m;
    for(int i=0; i<n; i++)
    {
        cin>>tmp;
        m[tmp]=-1;             //去重，因为最佳匹配不能重复
    }
    for(int i=0; i<n; i++)
    {
        cin>>tmp;
        if(m.find(tmp) != m.end() && m[tmp] == -1)     //a中出现，只匹配一次
        { 
            count++;
            m[tmp]=1;
        }
    }
    if(count < m.size())  //A中有未匹配的元素，因此B中可以修改增加一个匹配
        count++;
    else if(count == n )         //A中无重复元素，且全部匹配完成，则无论B改了什么都会-1
        count--;
    else 
        count = count;           //此处A中有重复元素，则不会减少
    cout<<count<<endl;
    return 0;
}

发表于 2019-08-31 19:36:26 回复(0)
哼哼哈哈呵呵头像 哼哼哈哈呵呵
数的范围多大都不说 最***就是这种题了
发表于 2019-08-19 16:39:52 回复(0)
正在卷的三文鱼很讨厌吃香菜头像 正在卷的三文鱼很讨厌吃香菜 
import java.util.Scanner;
import java.util.Arrays;
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[N];
        for(int i=0;i<N;i++){
            A[i]=sc.nextInt();
        }
        for(int i=0;i<N;i++){
            B[i]=sc.nextInt();
        }
        /*
        先排序，利用双指针求解
        */
        Arrays.sort(A);
        Arrays.sort(B);
        int count=0;
        //flag用于检查A和B是否完全相等
        boolean flag=false;
        int i=0,j=0;
        while(i<N && j<N){
            if(A[i]==B[j]){
                i++;
                j++;
                count++;
            }else if(A[i]>B[j]){
                j++;
                flag=true;
            }else{
                i++;
                flag=true;
            }
        }
        if(flag){
            System.out.println(count+1);
        }else{
            System.out.println(N-1);
        }
    }
}
先排序，双指针解法
发表于 2019-07-31 22:15:42 回复(0)
爱吃土豆的熊猫人头像 爱吃土豆的熊猫人
import java.util.*;
public class Main{
    public static void main(String[] args){
        int count=0;
        Scanner scanner = new Scanner(System.in);
        //打印数组长度
        int n = scanner.nextInt();
        //创建第一个数组
        ArrayList<Integer> a = new ArrayList<Integer>();
        for(int i=0;i<n;i++){
           int num = scanner.nextInt();
            a.add(num);
        }
        //创建第二个数组
         ArrayList<Integer> b = new ArrayList<Integer>();
        for(int i=0;i<n;i++){
           int num1 = scanner.nextInt();
            b.add(num1);
        }
        //如果两个数组相等
        if(a.equals(b)){
            System.out.println(sort1(a,b,n)-1);
        }else if(rev(a,b)){
           
            System.out.println(sort1(a,b,n)-1);
        }else{
            System.out.println(sort1(a,b,n));
        }
      
    }
    public static int sort1(ArrayList<Integer> a,ArrayList<Integer> b,int n){
        int count=0;
        for(int k=0;k<n;k++){
            for(int p=0;p<n;p++){
                if(a.get(k)==b.get(p)){
                    count++;
                }
            }
        }
        return count;
    }
   
    public static boolean rev(ArrayList<Integer> a,ArrayList<Integer> b){
      
        Collections.reverse(b);
        if(a.equals(b)){
            return true;
        }else{
            return false;
        }
       
    }
   
}
发表于 2019-06-29 17:59:53 回复(0)
提交观点

问题信息

C++工程师 贪心 数组 算法工程师 2019 寒武纪 排序 Java工程师
来自：寒武纪2019秋招软件...
上传者：小小
难度：
21条回答 7910浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最佳配对

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号