5: Minimize Unfairness

uuuouou

即从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. };

复制代码