给定数组中2个元素之间的最小距离
在比赛中,他们要求写一个C函数,它返回给定数组中X和Y之间的最小距离,其中X和Y是数组的元素。提供X和Y是不同的。给定数组中2个元素之间的最小距离
如果已经写了一段代码,但是代码运行到许多if
的和else
的,
我的代码(有一些错误):
int getMinXYDist(int arr[],int n,int x,int y){
int i,flag = 0,ele = -1 ,dist = 0;
int minDist = 1000; // SETTING minDist TO MAX VALUE.
for(i = 0 ; i< n; i++)
if(arr[i] == x || arr[i] == y){
if(flag == 0){
flag = 1;
ele = arr[i]==x?x:y;
dist = 0;
}
else{
if(ele == x){
if(arr[i] == y){
minDist = dist < minDist ? dist : minDist;
dist = 0;
ele = y;
}
else //if(arr[i] == x){
dist = 0;
}
else { //if(ele == y)
if(arr[i] == x){
minDist = dist < minDist ? dist : minDist;
dist = 0;
ele = x;
}
}
}
}
else {
if(flag == 1)
dist++;
}
return minDist;
}
void main(){
int arr = {6,1,5,1,8,6,3,4};
printf("\n%d" ,getMinXYDist(arr,sizeof(arr)/sizeof(int),6,5)); //Must return 2.
}
可以在任何一个建议一个更智能的方式[就像O(n)时间复杂度]计算距离一样?
如果找到x或y,请记录找到的索引。找到两者后,每找到一个,计算包含其他值的最后一个索引的距离。如果距离低于之前的最小值,则更新最小值。
int getMinXYDist(int arr[],int n,int x,int y)
{
int i, indexX, indexY;
int foundX = 0;
int foundY = 0;
int curDist;
int minDist = n;
for (i = 0; i < n; i++)
{
if (arr[i] == x)
{
foundX = 1;
indexX = i;
if (foundX && foundY)
{
curDist = indexX - indexY;
if (curDist < minDist)
{
minDist = curDist;
}
}
}
else if (arr[i] == y)
{
foundY = 1;
indexY = i;
if (foundX && foundY)
{
curDist = indexY - indexX;
if (curDist < minDist)
{
minDist = curDist;
}
}
}
}
return minDist;
}
基本上,我认为OP的解决方案是已经最佳,下界这个算法是n
步骤,即,在一次迭代中完成。
// if -1 is returned, then none of x and y are in the array
// if n is returned, then one of x and y is not in the array
// otherwise, mindist(x, y) is returned.
int test(int v[], int n, int x, int y)
{
int flag = -1;
int i, a = -1, b = -1, dist = n;
for (i = 0; i < n; ++i) {
if (v[i] == x) {
flag = 0;
a = i;
break;
} else if (v[i] == y) {
flag = 1;
b = i;
break;
}
}
if (flag < 0) return -1; // x and y are both not in array;
for (++i; i < n; ++i) {
if (v[i] == x) {
if (0 == flag) a = i;
else {
flag = 0;
if (i - b < dist) dist = i - b;
a = i;
}
} else if (v[i] == y) {
if (1 == flag) b = i;
else {
flag = 1;
if (i - a < dist) dist = i - a;
b = i;
}
}
}
return dist;
}
int minDistance (int arr[], int n, int x, int y) {
if(x == y) return 0;
int index1 = -1;
int index2 = -1;
int minvalue = n;
for(int i = 0 ; i < n; i++){
if((arr[i] == x) && ((i-index2) < minvalue)){
index1 = i;
if(index2 != -1)minvalue = i-index2;
}else if((arr[i] == y) && ((i-index1) < minvalue)){
index2 = i;
if(index1 != -1)minvalue = i-index1;
}
}
return minvalue;
}
其中
-
n
:阵列的大小。 -
x
andy
:两个输入数组的数量。
如果返回minvalue
是n
然后x
或y
不存在于阵列。
复杂性:O(n),一遍。
n:阵列的大小。 x和y:两个输入数组的数量。 如果返回的minvalue是n,则x或y不在数组中。 复杂性:O(n),一遍。 – 2013-07-30 19:32:04
欢迎来到stackoverflow。请享用。您可以使用编辑链接更新您的问题。 – 2013-07-30 19:48:31
距离可能是负值吗?或绝对值? – gongzhitaao 2013-04-10 19:43:14
@ gzhzhizaoao无距离不能消极。 – 2013-04-10 19:43:46
@ gongzhitaao如果我的阵列是6 1 5 8 2 8 4 6,dist和1和6以及6和1是相同的。并且距离为1. – 2013-04-10 19:44:39