|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
即从n个数中找出k个使得k个数中的最大值和最小值之差最小,很明显我们需要选最接近的k个数,所以trivial的方式即将这n个数排序,然后遍历k个数的选择,时间O(nlogn+n)- class Solution {
- public:
- int minimizeUnfairness(vector<int> &a, int k) {
- sort(a.begin(), a.end());
- int n = a.size(), res = a[n-1] - a[0];
- for(int i = 0; i+k <= n; ++i){
- res = min(res, a[i+k-1] - a【i】);
- }
- return res;
- }
- };
复制代码
|
|