Min Amplitude

这是一道google的oa题, 给一个数组, 通过改变三个数后, 使得数组最大值和最小值的差, 最小.

狗家的题都是先观察, 然后再coding, 主要是找到好的思路. 这题也是这样, 首先观察我们可以使用的操作, 就是改变数组中任意的三个数. 因为最后求最值的差, 所以这三个数的选择肯定是选择和最值有关的数. 首先排序一下, 然后找到两头(最大数列,和最小数列). 发现因为只有三个数可以改变, 那么改变后的最值肯定出在以下几种情况: 改变了最小的三个值, 答案= 第四小的值与最大值的差…由此类推即可发现答案有四种可能.

具体实现上, 因为要找到最大的四个数和最小的四个数, 可以sort, 也可以用priority queue.

#include <iostream>  // std::cout
#include <algorithm> // std::lower_bound, std::upper_bound, std::sort
#include <vector>    // std::vector
#include <queue>    // std::priority_queue
#include <float.h>
#include <cstdlib>
using namespace std;

/**
 * *
 * 
 *  Given an Array A,
 *  find the minimum amplitude you can get after changing up to 3 elements.
 *  Amplitude is the range of the array 
 *  (basically difference between largest and smallest element).
 * 
 * Input: [-1, 3, -1, 8, 5 4]
 * Output: 2
 * Explanation: we can change -1, -1, 8 to 3, 4 or 5
 * 
 * Input: [10, 10, 3, 4, 10]
 * Output: 0
 * Explanation: change 3 and 4 to 10
 * **/
int Amplitude(vector<int> nums) {
    priority_queue<int, vector<int>, greater<int>> max_q;
    priority_queue<int, vector<int>, less<int>> min_q;
    
    for(auto n : nums) {
        max_q.push(n);
        min_q.push(n);
    }

    if(nums.size() < 3)
        return 0;
    int res = std::numeric_limits<int>::max();
    int max_ary[4];
    int min_ary[4];
    for (int i = 0; i < 4; i++)
    {
        max_ary[i] = max_q.top();
        min_ary[i] = min_q.top();
        max_q.pop();
        min_q.pop();
    }
    res = min(res, abs(min_ary[0] - max_ary[3])); 
    res = min(res, abs(min_ary[3] - max_ary[0]));
    res = min(res, abs(min_ary[1] - max_ary[2]));
    res = min(res, abs(min_ary[2] - max_ary[1]));

    return res;
}
int main()
{
    vector<int> test1 = {-1, 3, -1, 8, 5, 4};
    vector<int> test2 = {10, 10, 3, 4, 10};
    vector<int> test3 = {10, 3, 4, 10};

    cout << Amplitude(test1) << endl;
    cout << Amplitude(test2) << endl;
    cout << Amplitude(test3) << endl;
    
    return 0;
}