Halo

A magic place for coding

0%

CCF--最小差值问题

最小差值问题

问题描述

 给定n个数,请找出其中相差(差的绝对值)最小的两个数,输出它们的差值的绝对值。

输入格式

 输入第一行包含一个整数n
第二行包含n个正整数,相邻整数之间使用一个空格分隔。

输出格式

输出一个整数,表示答案。

样例输入

5
1 5 4 8 20

样例说明

相差最小的两个数是5和4,它们之间的差值是1。

样例输入

5
9 3 6 1 3

样例输出

0

样例说明

有两个相同的数3,它们之间的差值是0。

数据规模和约定

对于所有评测用例,2≤ n ≤1000,每个给定的整数都是不超过10000的正整数。

解决方法

 主要思路:首先通过排序将数组中的数据有序化,由于最小的差值只会出现在有序数组的两个相邻的数中,因此,只需要求出有序数组中每两个相邻的数的差值即可,再从中找出最小的一个。此种算法也是效率最高的一种。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
int num;
cin >> num;
int arr[num];
int i = 0;
int n = num;
while (n--) {
cin >> arr[i++];
}

sort(arr, arr+num);

int diff[num - 1];
for (int j = 0; j < num-1; j++) {
diff[j] = arr[j+1] - arr[j];
}

int min;
if (num > 2) {
min = arr[1] - arr[0];
for (int k = 0; k < num-1; k++) {
if (diff[k] < min)
min = diff[k];
}
}
else {
min = diff[0];
}

cout << min << endl;
return 0;
}

最小差值问题的讲解到这里结束了,谢谢!

Welcome to my other publishing channels