数组元素最小差值 C++实现

问题描述：给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。
输入格式：输入第一行包含一个整数n。第二行包含n个正整数，相邻整数之间使 用一个空格分隔。
输出格式：输出一个整数，表示答案。
输入:
5
1 5 4 8 20
输出:
1
输入：
5 9 3 6 1 3
输出
0
数据规模和约定：对于所有评测用例，2 ≤ n ≤ 1000，每个给定的整数都是不超过10000的正整数。

直接能够想到的是用algorithm库中的sort函数进行排序后，最小两个元素之间的差值即为答案，算法复杂度O（nlog2n）

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[100000] = {0};
int n;
cin >> n;
for (int i = 0; i < n;++i)
{
cin >> a[i];
}
sort(a, a + n);
cout << a[1] - a[0] << endl;
return 0;
}

以下分享以下自己想到的另外一种方法，通过三个整形变量，分别记录最小差值，以及数组中的元素。应该是种动态规划，不知道是不是，改进之后算法时间复杂度为O（n）

#include<iostream>
#include<cmath>
using namespace std;
//数组中元素最小差
void fun(int a[],int n)
{
if(n==1)
{
return;
}
int num1=a[1];//初始标记数组第二位
int num2=a[0];//初始标记数组第一位
int sum = abs(num1-num2);//记录差
for (int i = 2; i < n;i++)
{
if(a[i]<num1)
{
num1 = a[i];
if(abs(num1-num2)<sum)
{
sum = abs(num1 - num2);//更新最小差
num2 = num1;//更新num2
num1 = a[i + 1];//更新num1
}
}
}
cout << sum << endl;
}
int main()
{
int a[5]={100,122,150,1010,99};
fun(a, sizeof(a) / sizeof(int));
return 0;
}

最后

以上就是独特爆米花为你收集整理的数组元素最小差值 C++实现的全部内容，希望文章能够帮你解决数组元素最小差值 C++实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。