最小差值
题意
给你一个数组a,请你求出数组a中任意两个元素间差的最小值。(a的长度至少为2且长度不超过 )
解法1
可以用枚举法求出两两差值的最小值
时间复杂度:
空间复杂度:
代码
class Solution { public: /** * 求最小差值 * @param a int整型vector 数组a * @return int整型 */ int minDifference(vector<int>& a) { int n=a.size(); int ans=2147483647; for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) ans=min(ans,abs(a[i]-a[j])); return ans;// write code here } };
解法2
以上解法时间复杂度太高,无法通过所有测试数据。
我们先将数组a进行排序,这样最小差值必然是排序后数组某两个相邻元素的差。
时间复杂度:
空间复杂度:
代码
class Solution { public: /** * 求最小差值 * @param a int整型vector 数组a * @return int整型 */ int minDifference(vector<int>& a) { int n=a.size(); sort(a.begin(),a.end()); int ans=2147483647; for(int i=0;i<n-1;i++) ans=min(ans,abs(a[i]-a[i+1])); return ans;// write code here } };