数组中两个字符串的最小距离问题

用户11458826

发布于 2025-01-23 09:10:06

4200

代码可运行

文章被收录于专栏：杀马特杀马特

运行总次数：0

代码可运行

一·题目：

牛客网题目链接：数组中两个字符串的最小距离_牛客题霸_牛客网

二·思路：

一开始就是二话没想看到时间复杂度是o(N)就想到肯定不能直接来回遍历去寻找，于是就想到把出现str1和str2下标记录下来然后去比较差值。于是，就搞了，下面复杂版的代码后面展示，不过这里更推荐下面的那种简单的解法

这里有简单的思路也就是后面看了大佬的题解才发现利用指针记录下标完全把问题简单话了，下面看一下具体思路：

思路：主要说下写法1：即它说复杂度要o(n)故也就是对这个strs只能走一遍，因此，还要判断str1，str2的下标最小值，故这里用个min函数，也就说最优就是当我们遍历的时候就边比较距离并求min，只要遇到str1，str2就记录，i每动一次，就有可能导致下标变化因此就可能导致求min，注：绝对值求距离。

三·代码：

3.1复杂版解答：

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;



int main() {
    int ret = 0x3f3f3f3f;//整型最大值
    int n;
    cin >> n;
    getchar();//读取cin剩下的\n
    string str1, str2;
    getline(cin, str1, ' ');
    getline(cin, str2);//由题可知是\n为最后一个终止符
    vector<string> strs;
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);
        strs.push_back(s);
    }
    int flag1 = 0, flag2 = 0;
    for (int i = 0; i < strs.size(); i++) {//判断是否在strs都出现了
        if (str1 == strs[i]) flag1 = 1;
        if (str2 == strs[i]) flag2 = 1;
    }
    if (flag1 == 1 && flag2 == 1) {
        set<int> v1, v2;
        //使用set对下标排序：
        for (int j = 0; j < strs.size(); j++) {
            if (strs[j] == str1) {
                v1.insert(j);

            }
            if (strs[j] == str2) {
                v2.insert(j);


            }
        }
        set<int> s, f;

        if (v1.size() < v2.size()) s = v1, f = v2;
        else s = v2, f = v1;
        for (auto a : s) {
            //这里遍历短的那个下标数组，去长的中找比它大或比它小，差就有可能是
            auto cur = f.upper_bound(a);
            if (cur != f.begin()) {
                auto tmp = --cur;//set支持双向迭代器，会改变cur
                cur++;
                ret = min(ret, abs(*(tmp) - a) > abs(*(cur) - a) ? abs(*(cur) - a) : abs(*
                          (tmp) - a));
            } else ret = min(ret, *(cur) - a);
        }

    }
    if (ret != 0x3f3f3f3f) cout << ret << endl;
    else cout << -1 << endl;

}

3.2优化版本：

#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
int main() {
    int n;
   cin>>n;
   getchar();
   string str1,str2;
   getline(cin,str1,' ');
   getline(cin,str2);
   vector<string> v(n);
   int ret=0x3f3f3f3f;
   int pre1=-1,pre2=-1;
   for(int i=0;i<n;i++) cin>>v[i];
   for(int i=0;i<n;i++){
     if(v[i]==str1) pre1=i;
     if(v[i]==str2) pre2=i;
     if(pre1!=-1&&pre2!=-1) ret=min(ret,abs(pre1-pre2));
   }
   if(pre1==-1||pre2==-1) cout<<-1<<endl;//存在str1或者str2中的一个也是-1
   else cout<<ret<<endl;



}