牛牛分数组

[编程题]牛牛分数组

热度指数：537 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛面前有一堆数，他想把这些数分成两堆，只不过牛牛是一个很有想法的人。

他希望分得的两堆数能够满足，第一堆数的最大值和第二堆数的最小值差值最小。

由于数太多，牛牛犯了难，所以他想请你帮帮他，给定n个数，返回符合牛牛希望的分法中最小的差值是多少。

示例1

输入

2,[1,2]

输出

说明

只有一种分发，分成的两堆数中第一堆数的最大值与第二堆数的最小值差值最小为1。

示例2

输入

6,[2,4,3,3,1,2]

输出

说明

在所有分法中，第一堆数分成[2,1]，第二堆数分成[3,2,4,3]，分成的两堆数中第一堆数的最大值与第二堆数的最小值差值最小为0。

备注:

算法知识视频讲解

C/C++

VatalityWang

 /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回符合牛牛希望的分法中最小的差值是多少
     * @param n int整型 代表共有多少数
     * @param a int整型vector 代表每个数的大小
     * @return int整型
     */
    int splitArray(int n, vector<int>& a) {
        // write code here
        sort(a.begin(),a.end());
        vector<int> diff;
        for(int i=0;i<a.size();i++)
            if(i<a.size()-1)
                diff.push_back(a[i+1]-a[i]);
        return *std::min_element(diff.begin(),diff.end());
    }

编辑于 2021-04-23 20:50:35 回复(0)

牛客377646584号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回符合牛牛希望的分法中最小的差值是多少
# @param n int整型代表共有多少数
# @param a int整型一维数组代表每个数的大小
# @return int整型
#
class Solution:
def splitArray(self , n , a ):
# write code here
a = sorted(a)
res = a[1]-a[0]
for i in range(n-1):
res = min(res,a[i+1]-a[i])
return res

发表于 2021-04-23 12:31:30 回复(0)

---459---

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回符合牛牛希望的分法中最小的差值是多少
     * @param n int整型 代表共有多少数
     * @param a int整型vector 代表每个数的大小
     * @return int整型
     */
    int splitArray(int n, vector<int>& a) {
        // write code here
        sort(a.begin(), a.end());
        int res = a[1] - a[0];
        for(int i = 2; i < n; i++){
            res = min(res, a[i] - a[i - 1]);
        }
        return res;
    }
};

发表于 2021-03-07 13:17:35 回复(0)