【题解】最小差值

最小差值

题意

给你一个数组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
    }
};
全部评论

相关推荐

码农索隆:有点耳熟,你们是我教过最差的一届
点赞 评论 收藏
分享
Twilight_m...:经典我朋友XXXX起手,这是那种经典的不知道目前行情搁那儿胡编乱造瞎指导的中年人,不用理这种**
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务