【数组的距离】-题解(C++代码)——高效算法

889 阅读 0 评论 0 点赞

解题思路：
	这个思路是我参考了大佬的思路，只是大佬没给出代码，我就顺着大佬的思路做了下来。把两个数组合并排序：
1 3 2 6 5
4 8 7 9 0
得到 ：0 1 2 3 4 5 6 7 8 9
把相邻的，且为来自两个不同数组的元素，相减求出距离，再选出最小距离。

注意事项：
1.思路很简单，需要四个数组，x[],y[],z[],set[]。
2.x,y存放题目所给数组，z存放混合后的数组，set对应当前元素所来自的数组，set[i]=1说明来自数组x，set[i]=2说明来自数组y。
3.利用快速排序对z[]及对应set进行排序。

参考代码：
```cpp
#include<iostream>
using namespace std;
void swap(int &a, int &b)
{
	int tmp = a;
	a = b;
	b = tmp;
}
void QuickSort(int a[], int b[], int s, int e)
{
	if (s >= e)
		return;
	int k = a[s];
	int i = s, j = e;
	while (i != j)
	{
		while (j > i&&a[j] >= k)
			j--;
		swap(a[i], a[j]);
		swap(b[i], b[j]);
		while (i < j&&a[i] <= k)
			i++;
		swap(a[i], a[j]);
		swap(b[i], b[j]);
	}   //a[i]=k
	QuickSort(a, b, s, i - 1);
	QuickSort(a, b, i + 1, e);
}
int main()
{
	int x[1001],y[1001],z[2001],set[2001];
	int m,n;
	cin>>m>>n;
	int i;
	for(i=0;i<m;i++)
		cin>>x[i];
	for(i=0;i<n;i++)
		cin>>y[i];
	for(i=0;i<m;i++)
	{
		z[i]=x[i];
		set[i]=1;
	}
	int j=0;
	for(;i<m+n;i++)
	{
		z[i]=y[j++];
		set[i]=2;
	}
	QuickSort(z,set,0,m+n-1);
	int min=1001;
	for(i=0;i<m+n;i++)
	{
		for(j=i+1;j<m+n;j++)
		{
			if(set[i]!=set[j])
			{
				if(z[j]-z[i]<min)
					min=z[j]-z[i];
			}
		}
	}
	cout<<min;
	
	return 0;
}
```

0.0分

3 人评分

本文分类：题解列表
浏览次数：889 次浏览
发布日期：2019-08-07 09:30:49
本文链接：https://blog.dotcpp.com/a/61135

上一篇 > Lucky Word-题解(C语言代码)
下一篇 > 【排队买票】（C++代码）——简单递归

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

【数组的距离】-题解(C++代码)——高效算法

评论列表共有 0 条评论

发表评论取消回复

【数组的距离】-题解(C++代码)——高效算法

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复