首页 > 试题广场 >

最佳配对

[编程题]最佳配对
  • 热度指数:3741 时间限制: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
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)
#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)
#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)
#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)
#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)
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)
#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)
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)
使用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)
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)
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)
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)
我的 思路清晰
#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)
#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)
这道题的测试用例太简单了。。情况还是比较多的,感觉大家的答案考虑的都有问题
考虑一下几种情况:
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)