找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 582|回复: 0
收起左侧

[资源分享] 5: Minimize Unfairness

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 01:21 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
即从n个数中找出k个使得k个数中的最大值和最小值之差最小,很明显我们需要选最接近的k个数,所以trivial的方式即将这n个数排序,然后遍历k个数的选择,时间O(nlogn+n)
  1. class Solution {
  2. public:
  3.         int minimizeUnfairness(vector<int> &a, int k) {
  4.                 sort(a.begin(), a.end());
  5.                 int n = a.size(), res = a[n-1] - a[0];
  6.                 for(int i = 0; i+k <= n; ++i){
  7.                         res = min(res, a[i+k-1] - a【i】);
  8.                 }
  9.                 return res;
  10.         }
  11. };
复制代码




您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表