数组中两个字符串的最短距离---一题多解（贪心/二分）

点击跳转到题目

方法：贪心 / 二分

目录

贪心：

二分：

贪心：

要找出字符串数组中指定两个字符串的最小距离，即找出指定字符串对应下标之差的最小值

思考：如果是直接暴力求解，需要两层for循环，依次判断是否是指定字符串，如果是，则找出当前指定字符串的最小距离；时间复杂度O（N^2），题目给的数据范围是10^5，是过不了的；

我们基于暴力求解的思路拓展，暴力解法中，我们在找每一个指定字符串的最小距离时，都是针对该字符串位置逐一枚举，那如果优化一下找指定字符串最小距离的方法呢？

在遍历数组的过程中，用两个变量记录str1、str2的最近下标，对于遍历到的每一个str1、str2，我们都计算该字符串与其左边元素中最小距离（因为左边元素是已经更新过了最近的下标），这样遍历一遍数组，更新保存最小值，即可。

时间复杂度为O（N）

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

const int N = 1e5 + 10;
string a[N];

int main()
{
	int n;
	cin>>n;
	string str1,str2;
	cin>>str1>>str2;
	for(int i=0;i<n;i++) cin>>a[i];
	int prev1,prev2;//str1、str2的最近下标
	prev1 = prev2 = -1;
	int ret = 1e6;
	
	//对于每个str1、str2，只计算他们左边的最近字符串
	for(int i=0;i<n;i++)
	{
		if(a[i] == str1)
		{
			if(prev2 != -1)
			{
				int t = i - prev2;
				ret = min(ret,t);
			}
			prev1 = i;
		}
		else if(a[i] == str2)
		{
			if(prev1 != -1)
			{
				int t = i - prev1;
				ret = min(ret,t);
			}
			prev2 = i;
		}
	}
	
	if(prev1 == -1 || prev2 == -1) cout<<-1<<endl;
	else cout<<ret<<endl;
	return 0;
}

二分：

要找出指定字符串对应下标之差的最小值，下标，是个天然有序的排列，具有单调性

开俩个vector，分别保存str1、str2在原数组中的下标，两个vector内存的元素都是单调递增且互相之间没有交集，对于枚举vector1内的所有元素在vector2中的边界，左边都小于vector1，右边都大于vector1，此时边界两边的l、r对应的，与vector1相减，一定是当前字符串的最小值。

时间复杂度为O（nlogm），其中n+m = N

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

const int N = 1e5 + 10;
string a[N];
vector<int> v1,v2; //分别存放str1、str2在a中的位置

int main()
{
	int n;
	string str1,str2;
	cin>>n>>str1>>str2;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		if(a[i] == str1) v1.push_back(i);
		if(a[i] == str2) v2.push_back(i);
	}
	
	
	if(v1.empty() || v2.empty())
	{
		cout<<-1<<endl;
		return 0;
	}
	
	int ret = 1e6;
	//枚举v1，二分v2
	for(int i=0;i<v1.size();i++)
	{
		int l = -1, r = v2.size();
		while(l + 1 < r)
		{
			int mid = l + r >> 1;
			if(v1[i] < v2[mid])
				r = mid;
			else
				l = mid;
		}
		//需要考虑到边界在v2的首尾时
		int t;
		if(l == -1)  t = v2[r] - v1[i];
		else if(r == v2.size())  t = v1[i] - v2[l];
		else  t = min(v2[r] - v1[i],v1[i] - v2[l]);
		ret = min(ret,t);
	}
	cout<<ret<<endl;
	return 0;
}