给定一个string数组article（有单词构成）和数组中元素的个数n，同时给定数组中的两个单词x和y。请返回这两个单词的最短距离（比如两个单词分别在第1和第3个位置，则最短距离为2）。保证两个单词不相同且均在数组中出现，同时保证数组中单词数小于等于1000。
[编程题]单词最近距离
//时间复杂度为O(n),空间复杂度O（1）。
//总的思想就是设置一个游标记录上一个出现的x或者y的位置。游标初始化为-1，最短距离设置为n。
//当遇到第一个x或y时，游标设置为当前位置。接下来（1）再遇到相同字符串时，只需将游标设置
//为当前位置，原因是，在两个相同字符串中间没有出现另一个需要查找的字符串，则即使接下来出
//现了另一个字符串，也只会距离当前位置的最近。（2）遇到需要查找的第二个字符串，则计算两
//者之间的距离,判断是否比最短距离还短，若是，则更新最短距离。完事后需要将游标设为当前位置
//。接下来就明朗了，要么遇到不同的另一个字符串或者同一个，按上述循环即可。代码如下：
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y) {
// write code here
if(n <= 0) return -1;
int mindis=n;
int point=-1;
for(int i = 0; i < n; i++){
if(article[i] == x || article[i] == y ){
if(point != -1 && article[i] != article[point] && mindis > i-point) mindis=i-point;
point=i;
}
}
return mindis;
}
};
发表于 2018-06-27 14:02:10
回复(3)
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y) {
// write code here
int px=0,py=0,result=n;
for(int i=0;i<n;i++){
if(article[i]==x)
px=i;
else if(article[i]==y)
py=i;
if(px!=0&&py!=0)//确保x和y都至少找到了一个。
result=min(abs(px-py),result);
}
return result;
}
};
发表于 2015-08-07 21:31:55
回复(2)
public class Distance {
public int getDistance(String[] s, int n, String x, String y) {
//两个单词均在文中出现且不相同
int startX=-1, endY = -1;//1和0之间间隔为1
int minD = Integer.MAX_VALUE;
for(int i=0; i<s.length; i++){
if(s[i].equals(x)) startX=i;
else if(s[i].equals(y)) endY=i;
else continue;
//两个元素的距离:startX-endY的绝对值，与当前记录的最小间距minD比，取小的
if(startX!=-1 && endY!=-1) minD=Math.min(Math.abs(startX-endY), minD);
}
return minD;
}
}
发表于 2016-08-20 14:44:40
回复(0)
//游标卡尺原理，每次找到一个x或y，就计算一次距离，然后更新游标位置
class Distance {
public:
int getDistance(vector article, int n, string x, string y) {
// write code here
int min_dist = INT_MAX;
int x_ind = -1,y_ind = -1;
for(int i=0;i<n;++i)
{
if(article[i] == x)
{
if(y_ind != -1)
{
min_dist = min(min_dist,abs(i-y_ind));
}
x_ind = i;
}
if(article[i] == y)
{
if(x_ind != -1)
{
min_dist = min(min_dist,abs(i-x_ind));
}
y_ind = i;
}
}
return min_dist;
}
};
发表于 2020-07-15 22:55:06
回复(0)
//O(n) 维护两个标志位：以x开始和以y开始的标志
int getDistance(vector<string> article, int n, string x, string y) {
int sx = -1,sy = -1;
int ans = INT_MAX;
for(int i=0;i<n;++i){
if(article[i] == x){
if(sx <= i)sx = i;
if(sy > -1){
ans = min(ans,i-sy);
sy = -1;
}
}
if(article[i] == y){
if(sy <= i)sy = i;
if(sx > -1){
ans = min(ans,i-sx);
sx = -1;
}
}
}
return ans;
}
编辑于 2019-09-07 23:08:47
回复(0)
public int getDistance(String[] article, int n, String x, String y) {
int ans = 1001;
for(int i=0;i<article.length;i++){
if(article[i].equals(x)){
tempX = i;
if(Math.abs(tempX-tempY) < ans){
ans = Math.abs(tempX - tempY);
}
}
if(article[i].equals(y)){
tempY = i;
if(Math.abs(tempX-tempY) < ans){
ans = Math.abs(tempX - tempY);
}
}
}
return ans;
}
// write code here
//记录当前X、Y位置即可，然后遍历一遍寻找最小值
//时间复杂度O(n) 空间复杂度O(1)
int tempX = -1001,tempY = -1001;int ans = 1001;
for(int i=0;i<article.length;i++){
if(article[i].equals(x)){
tempX = i;
if(Math.abs(tempX-tempY) < ans){
ans = Math.abs(tempX - tempY);
}
}
if(article[i].equals(y)){
tempY = i;
if(Math.abs(tempX-tempY) < ans){
ans = Math.abs(tempX - tempY);
}
}
}
return ans;
}
发表于 2019-03-17 14:15:07
回复(0)
总觉得可以很高效解决的，想太多有点想糊涂了，所以还是简单处理一下，有个印象再来讨论区看一下大家的高明做法。
public class Distance {
public int getDistance(String[] article, int n, String x, String y) {
// write code here
Vector<Integer> vc = new Vector<>();
for (int i=0; i<n; i++){
if (x.equals(article[i])){
vc.add(i);
}
}
int min = Integer.MAX_VALUE;
for (int i=0; i<n; i++){
if (y.equals(article[i])){
for (Integer num:vc){
if (Math.abs(i-num) < min){
min = Math.abs(i-num);
}
}
}
}
return min;
}
}
倒是时间40ms,空间9932K
发表于 2017-08-26 20:30:31
回复(0)
记录每个词出现的位置，复杂度O(n)。
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y)
{
vector<int> posX, posY;
for (int i = 0; i < n; ++i)
{
if (article[i] == x) posX.emplace_back(i);
if (article[i] == y) posY.emplace_back(i);
}
int res = n;
for (int i = 0, j = 0; i < static_cast<int>(posX.size()); ++i)
{
while (j < static_cast<int>(posY.size()) && posY[j] < posX[i]) ++j;
if (j < static_cast<int>(posY.size())) res = min(res, abs(posY[j] - posX[i]));
if (j < static_cast<int>(posY.size() - 1)) res = min(res, abs(posY[j + 1] - posX[i]));
if (j > 0) res = min(res, abs(posY[j - 1] - posX[i]));
}
return res;
}
};
发表于 2017-07-01 16:34:24
回复(0)
public int getDistance(string[] article, int n, string x, string y)
{
int posx = -1;
int posy = -1;
int length = int.MaxValue;
for (int i = 0; i < n; i++)
{
if (article[i] == x)
{
posx = i;
if (posy != -1)
{
length = Math.Min(length, Math.Abs(posx - posy));
}
}
if (article[i] == y)
{
posy = i;
if (posx != -1)
{
length = Math.Min(length, Math.Abs(posx - posy));
}
}
}
return length;
}
发表于 2016-03-19 09:29:14
回复(0)
python三行解法
class Distance:
def getDistance(self, article, n, x, y):
arrX=[i for i,v in enumerate(article) if v==x]
arrY=[i for i,v in enumerate(article) if v==y]
return min([abs(i-j) for i in arrX for j in arrY])
进而可以简化成一行，甚为暴力：
return min([abs(i-j) for i in [index for index,v in enumerate(article) if v==x] for j in [index for index,v in enumerate(article) if v==y]])
不过似乎有点长，还是三行看起来更舒服啊
发表于 2017-11-15 20:38:06
回复(0)
import java.util.*;
/*
思路：因为单词可能重复，所以不能用HashMap，可以遍历过去，依次比较最小值，么得办法啦 就这样做吧
*/
public class Distance {
public int getDistance(String[] article, int n, String x, String y) {
if(article==null||article.length==0) return 0;
int min=n,countx=-1,county=-1;
for(int i=0;i<n;i++){//每一次所找到的x和y的下标都比较一次，取最小值即可
if(article[i].equals(x)) countx=i;
if(article[i].equals(y)) county=i;
if(countx!=-1&&county!=-1){
min =Math.min(Math.abs(countx-county),min);
}
}
return min;
}
}
运行时间：42ms
占用内存：9808k
发表于 2017-07-09 12:33:22
回复(0)
class Distance {
public:
const int N = 99999;
int getDistance(vector<string> article, int n, string x, string y) {
// write code here
if(n!= article.size()) return -1;
int xi = N;
int yi = N;
int res = N;
for(int i=0;i<n;++i) {
string &f = article[i];
if(f==x) {
xi = i;
}else if(f==y) {
yi = i;
}
if(xi!=N && yi!=N) {
res = min(abs(xi-yi), res);
}
}
return res;
}
};
发表于 2021-01-30 16:58:31
回复(0)
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y) {
// write code here
int minDiff = 0x7fffffff;
int xIdx = -1, yIdx = -1;
for (int i = 0; i < n; ++i) {
if (article[i] == x) {
xIdx = i;
}
if (article[i] == y) {
yIdx = i;
}
int diff = 0x7fffffff;
if (xIdx >= 0 && yIdx >= 0) {
diff = abs(xIdx - yIdx);
}
if (diff < minDiff) {
minDiff = diff;
}
}
return minDiff;
}
};
发表于 2020-08-01 21:48:12
回复(0)
数组article中，x和y最小距离必然是相邻两个x和y距离，所以遍历一次就能求出x和y的值
# -*- coding:utf-8 -*-
class Distance:
def getDistance(self, article, n, x, y):
# write code here
res=indx=indy=1000
for i,v in enumerate(article):
if v==x:
indx=i
res = min(res,abs(indx-indy))
elif v==y:
indy=i
res = min(res,abs(indx-indy))
return res
发表于 2019-07-15 10:58:04
回复(0)
// 遍历一次
// O(n)
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y) {
// write code here
int flag = 0;
int preIndex;
int minDistance = n;
for (int i = 0; i < n; ++i) {
if (article[i] == x || article[i] == y) {
if (article[i] == x) {
if (flag == 1) {
minDistance = min(minDistance, i - preIndex);
}
preIndex = i;
flag = -1;
}
else if (article[i] == y) {
if (flag == -1) {
minDistance = min(minDistance, i - preIndex);
}
preIndex = i;
flag = 1;
}
}
}
return minDistance;
}
};
运行时间：6ms
占用内存：504k
编辑于 2019-07-14 16:12:05
回复(0)
class Distance:
def getDistance(self, article, n, x, y):
# write code here
index1,index2=[],[]
ans=0x7fffffff
for i in range(n):
if article[i]==x:
index1.append(i)
elif article[i]==y:
index2.append(i)
if index1 and index2:
ans=min(ans,abs(index1[-1]-index2[-1]))
return ans
发表于 2019-06-28 08:30:09
回复(0)
1 开一个数组更新两个单词最新出现的位置 2 之所以这么做 是因为最小距离一定从近邻对中产生 3 时间复杂度O（n），空间复杂度O（1） class Distance: def getDistance(self, article, n, x, y): list1=[1001] * 2 mingap = 1000 for i in range(n): if article[i] == x: mingap = min(mingap,abs(list1[1]-i)) list1[0] = i if article[i] == y: mingap = min(mingap,abs(list1[0]-i)) list1[1] = i return mingap
发表于 2019-05-04 15:41:34
回复(0)
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y) {
// write code here
int res = n;
int px = -1, py = -1;
for(int i = 0; i < n; ++i){
if(article[i] == x){
px = i;
if(py != -1)
res = min(res, px-py);
}
else if(article[i] == y){
py = i;
if(px != -1)
res = min(res, py-px);
}
}
return res;
}
};
发表于 2018-11-29 00:53:49
回复(0)
class Distance {
public:
int getDistance(vector<string> article, int n, string x, string y)
{
// write code here
int pos_x=-1,pos_y=-1;
int min=INT_MAX;
for(int i=0;i<n;++i)
{
if(article[i]==x)
{
pos_x=i;
if(pos_y!=-1)
{
int tmp=pos_x-pos_y;
if(tmp<min)
min=tmp;
}
}
else if(article[i]==y)
{
pos_y=i;
if(pos_x!=-1)
{
int tmp=pos_y-pos_x;
if(tmp<min)
min=tmp;
}
}
}
return min;
}
};
发表于 2018-08-04 22:33:32
回复(0)
问题信息
难度：
49条回答
37收藏
19280浏览
通过挑战的用户
查看代码-
2022-12-05 00:15:55 -
2022-11-20 23:12:10
-
2022-10-13 23:22:20
-
2022-10-08 22:23:45
-
2022-09-13 07:49:10
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
