题目：

有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个数。

代码

$O(n^2)$

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
int a[N] = {4,1,2,3};
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>a[i];
    int min_diff = 0x3f3f3f3f,cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
        {
            if(min_diff > abs(a[j] - a[i]))
            {
                min_diff = abs(a[j] - a[i]);
                cnt = 1;
            }
            else if(min_diff == abs(a[j] - a[i]))
                cnt ++;
        }
    cout<<cnt<<endl;
    return 0;
}

$O(nlogn)$

我们发现题目中说所有元素均不同，那么排序之后，当前元素与下一个元素的差 必定是 当前元素与其余元素差的最小值。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100;
int a[N] = {4,1,2,3};
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++) cin>>a[i];
    sort(a,a+n);
    int min_diff = 0x3f3f3f3f,cnt = 0;
    for(int i = 0; i < n-1; i++)
        if(min_diff > abs(a[i+1] - a[i]))
        {
            min_diff = abs(a[i+1] - a[i]);
            cnt = 1;
        }
        else if(min_diff == abs(a[i+1] - a[i]))
            cnt ++;
    cout<<cnt<<endl;
    return 0;
}