Example:
WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));
assert(finder.distance("fox","the") == 3);
assert(finder.distance("quick", "fox") == 1);
我有以下解决方案,看起来是 O(n),但我不确定是否有更好的解决方案。有人知道吗?
String targetString = "fox";
String targetString2 = "the";
double minDistance = Double.POSITIVE_INFINITY;
for(int x = 0; x < strings.length; x++){
if(strings[x].equals(targetString)){
for(int y = x; y < strings.length; y++){
if(strings[y].equals(targetString2))
if(minDistance > (y - x))
minDistance = y - x;
}
for(int y = x; y >=0; y--){
if(strings[y].equals(targetString2))
if(minDistance > (x - y))
minDistance = x - y;
}
}
}
最佳答案
您的解决方案是 O(N^2)
因为您在查找每个单词时遍历整个列表。
首先找到第一个单词,然后再次遍历整个列表以找到第二个单词。
你可以做的是使用两个变量来跟踪每个单词的位置,并通过列表单次传递计算距离=> O(N)
.
int index1 = -1;
int index2 = -1;
int minDistance = Integer.MAX_VALUE;
int tempDistance = 0;
for (int x = 0; x < strings.length; x++) {
if (strings[x].equals(targetString)) {
index1 = x;
}
if (strings[x].equals(targetString2)) {
index2 = x;
}
if (index1 != -1 && index2 != -1) { // both words have to be found
tempDistance = (int) Math.abs(index2 - index1);
if (tempDistance < minDistance) {
minDistance = tempDistance;
}
}
}
System.out.println("Distance:\t" + minDistance);
关于java - 查找数组中单词之间的最小距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26876744/