L2-3 清点代码库

loopdeloop

于 2025-04-07 14:04:11 发布

阅读量454

点赞数 19

文章标签：算法 c++ 数据结构

本文链接：https://blog.csdn.net/loopdeloop/article/details/147042653

版权

上图转自新浪微博：“阿里代码库有几亿行代码，但其中有很多功能重复的代码，比如单单快排就被重写了几百遍。请设计一个程序，能够将代码库中所有功能重复的代码找出。各位大佬有啥想法，我当时就懵了，然后就挂了。。。”

这里我们把问题简化一下：首先假设两个功能模块如果接受同样的输入，总是给出同样的输出，则它们就是功能重复的；其次我们把每个模块的输出都简化为一个整数（在 int 范围内）。于是我们可以设计一系列输入，检查所有功能模块的对应输出，从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

输入格式：

输入在第一行中给出 2 个正整数，依次为 N（≤104）和 M（≤102），对应功能模块的个数和系列测试输入的个数。

随后 N 行，每行给出一个功能模块的 M 个对应输出，数字间以空格分隔。

输出格式：

首先在第一行输出不同功能的个数 K。随后 K 行，每行给出具有这个功能的模块的个数，以及这个功能的对应输出。数字间以 1 个空格分隔，行首尾不得有多余空格。输出首先按模块个数非递增顺序，如果有并列，则按输出序列的递增序给出。

注：所谓数列 { A1, ..., AM } 比 { B1, ..., BM } 大，是指存在 1≤i<M，使得 A1=B1，...，Ai=Bi 成立，且 Ai+1>Bi+1。

输入样例：

输出样例：

初始思路（大模拟，21/25分）

代码逻辑

输入存储：用二维数组 D 存储所有模块的输出。
去重统计：
- 用 C 存储不同的输出模式。
- 用 E 记录每个模式的重复次数。
- 遍历每个模块，检查是否已存在于 C 中，若存在则增加计数，否则新增模式。
排序输出：
- 每次遍历 E 找最大值，输出后标记为已处理。

问题分析

时间复杂度高：三重循环（最坏 O(N2⋅M)），导致部分测试点超时。
排序方式低效：每次找最大值而非一次性排序，增加额外开销。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int D[10005][105];
int C[10005][105];
int E[10005];
signed main()
{
	int a,b;
	cin>>a>>b;
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=b;j++)
		{
			cin>>D[i][j];
		}
	}
	int flag=1;
	for(int i=1;i<=b;i++)
	{
		C[1][i]=D[1][i];
	}
	
	for(int i=2;i<=a;i++)
	{
		int s=0;
	
		for(int j=1;j<=flag;j++) 
		{
			int tru=1;
			for(int k=1;k<=b;k++)
			{
				if(D[i][k]!=C[j][k])tru=0;
			}
			if(tru==1)
			{
				E[j]++;
				s=1;
				break;
			}
		}
		if(s==0)
		{
			for(int k=1;k<=b;k++)
			{
				C[flag+1][k]=D[i][k];
			}
			flag++;
		} 
	}
	cout<<flag<<endl;
	for(int k=1;k<=flag;k++)
	{
		int maxn=E[1];
		int flagg=1;
		for(int i=2;i<=flag;i++)
		{
			if(E[i]>maxn)
			{
				flagg=i;
				maxn=E[i];
			}
			if(E[i]==maxn)
			{
				for(int ss=1;ss<=b;ss++)
				{
					if(C[i][ss]>C[flagg][ss])
					{
						break;
					}
					if(C[i][ss]<C[flagg][ss])
					{
						flagg=i;
						maxn=E[i];
						break;
					}
				}
			}
		}
		
		cout<<E[flagg]+1<<" ";
		cout<<C[flagg][1];
		for(int j=2;j<=b;j++)
		{
			cout<<" "<<C[flagg][j];
		}
		cout<<endl;
		E[flagg]=-2;
	}
	return 0;
}

优化思路（AC 正解）

核心优化

利用 map<vector<int>, int> 去重和计数：
- vector<int> 存储输出序列，int 记录出现次数。
- 插入和查询的时间复杂度为 O(logK)，大幅降低比较次数。
一次性排序：
- 使用 sort 和自定义比较函数，确保按题目要求排序。

优化后代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 

signed main() {
    int a, b;
    cin >> a >> b;
    
    map<vector<int>, int> patternCount; // 用vector作为键，统计出现次数
    
    for (int i = 0; i < a; ++i) {
        vector<int> row(b);
        for (int j = 0; j < b; ++j) {
            cin >> row[j];
        }
        patternCount[row]++; // 统计该模式的出现次数
    }
    
    // 将map中的内容存入vector，方便排序
    vector<pair<vector<int>, int>> patterns(patternCount.begin(), patternCount.end());
    
    // 自定义排序规则：先按出现次数降序，次数相同则按字典序升序
    sort(patterns.begin(), patterns.end(), [](const auto& p1, const auto& p2) {
        if (p1.second != p2.second) {
            return p1.second > p2.second;
        }
        return p1.first < p2.first;
    });
    
    // 输出结果
    cout << patterns.size() << endl;
    for (const auto& p : patterns) {
        cout << p.second << " ";
        for (int j = 0; j < b; ++j) {
            if (j != 0) cout << " ";
            cout << p.first[j];
        }
        cout << endl;
    }
    
    return 0;
}