Min Amplitude
这是一道google的oa题, 给一个数组, 通过改变三个数后, 使得数组最大值和最小值的差, 最小.
狗家的题都是先观察, 然后再coding, 主要是找到好的思路. 这题也是这样, 首先观察我们可以使用的操作, 就是改变数组中任意的三个数. 因为最后求最值的差, 所以这三个数的选择肯定是选择和最值有关的数. 首先排序一下, 然后找到两头(最大数列,和最小数列). 发现因为只有三个数可以改变, 那么改变后的最值肯定出在以下几种情况: 改变了最小的三个值, 答案= 第四小的值与最大值的差…由此类推即可发现答案有四种可能.
具体实现上, 因为要找到最大的四个数和最小的四个数, 可以sort, 也可以用priority queue.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#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; } |