算法期中练习——1001. 最小差

算法期中练习——1001. 最小差

Description:

对于一个整数数列A[0], A[1], …, A[N-1]，要求在其中找两个数，使得它们的差的绝对值最小.
2 <= N <= 100, -1000 <= A[i] <= 1000.

Example:

例1：当A = {2, 7, -2}, 返回4.
例2：当A = {-8, 10, 30, 10}, 返回0.

请实现下面Solution类中计算minDifference(A)的函数，返回值为能得到的最小差.

class Solution {
public:
       int minDifference(vector<int> A) {
             
       }
};

---

分析：

定义一个变量difference，初始化为abs(A[1]-A[0])，或者为一个比较大的数，然后循环遍历求相邻两个数的差的绝对值，与difference比较，从而更新最小差值。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	int minDifference(vector<int> A) {
		int difference;
		sort(A.begin(), A.end());
		difference = abs(A[1] - A[0]);
		for (int i = 1; i < A.size() - 1; i++) {
			if (abs(A[i] - A[i + 1]) < difference) {
				difference = abs(A[i] - A[i + 1]);
			}
		}
		return difference;
	}
};
// another solution
class Solution {
public:
	int minDifference(vector<int> A) {
		int res, n;
		n = A.size();
		sort(A.begin(), A.end());
		res = 1000000000;
		for (int i = 0; i < n - 1; i++) res = min(res, A[i + 1] - A[i]);
		return res;
	}
};
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> A(n);
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	cout << s.minDifference(A) << endl;
	return 0;
}