查找 n 个数字数组中最接近的两个数字之间的距离。（预排序数组）

Question

数组经过预排序，使得算法 θ(nlogn) [排序+寻找最小距离]，与暴力算法 θ(n2) 相比。这两个代码做同样的工作，但第一个代码显示超过时间限制。我想知道错误是什么。代码中有错误吗？

带 while 循环的代码（超过时间限制）

#include <stdio.h>

void mindistance(int a[],int n)
{
    int i=1,arraymin=999,currentmin,current=a[0];

    while(i<n)
    {
        if(a[i]==current)
            i++;
        else
        {
            currentmin=a[i]-a[i-1];
            if(currentmin<arraymin)
            {
                arraymin=currentmin;
                current=a[i];
                i++;
            }

        }
    }
    printf("%d",arraymin);
}


int main(void)
{

    int a[]={4,34,56,77,99,424,754}; 
    mindistance(a,7);

    return 0;
}

使用 for 循环的代码（运行良好）

#include <stdio.h>

void mindistance(int a[],int n)
{
    int i,arraymin=999,currentmin,current=a[0],x,y;

    for(i=1;i<n;i++)
    {
        if(a[i]==current)
            continue;
        else
        {
            currentmin=a[i]-a[i-1];
            if(currentmin<arraymin)
            {
                arraymin=currentmin;
                current=a[i];

            }

        }
    }
    printf("%d",arraymin);
}


int main(void)
{

    int a[]={4,34,56,77,99,424,754};
    mindistance(a,7);

    return 0;
}

Answer 1

我相信您陷入了无限循环，因为您没有在每次迭代中都设置电流值。

Answer 2

循环不相同。在 for 循环中，i 在每次迭代中增加，而在 while 循环中，i 仅在某些情况下增加。一个相同的 while 循环是：

while(i<n)
{
    if(a[i]==current)
        i++;
    else
    {
        currentmin=a[i]-a[i-1];
        if(currentmin<arraymin)
        {
            arraymin=currentmin;
            current=a[i];
        }
        i++;
    }
}

查找 n 个数字数组中最接近的两个数字之间的距离。（预排序数组）

Finding the distance between the two closest numbers in an array of n numbers. (Presorted Arrays)

loops

array-algorithms

查找 n 个数字数组中最接近的两个数字之间的距离。 （预排序数组）

Finding the distance between the two closest numbers in an array of n numbers. (Presorted Arrays)

loops

array-algorithms

查找 n 个数字数组中最接近的两个数字之间的距离。（预排序数组）