A new Amazon intern encountered a challenging task.
Currently, the intern has n integers, where the value of the ith element is represented by the array element values[i].
The intern is curious to play with arrays and subsequences and thus asks you to join him.
Given an integer array values and an integer k, find the maximum and minimum median among all subsequences of length k.
Return an integer array in the form [maximum median, minimum median].
Example:
Given values = [1, 2, 3] and k = 2, the subsequences of length 2 are [1, 2], [1, 3], and [2, 3]. Their medians are 1, 1, and 2 respectively. The maximum median is 2 and the minimum median is 1.
Complete the function medians in the editor below.
medians has the following parameter(s):
values[n]: the array of integersk: the given integer
Returns
int[]: the maximum and minimum median among all subsequences of lengthkin the form[maximum median, minimum median].
这道 Amazon OA 题考察的是“排序 + 子序列中位数位置”的理解：因为题目要求在所有长度为 k 的子序列里找最大和最小中位数，而子序列不要求连续，所以只要先将数组排序，就能直接从有序序列中判断最有利的位置。对于长度为 k 的子序列，中位数对应的是排序后第 <code>(k+1)//2</code> 个位置（按题目样例可看出是偏左的中位数定义），因此最大中位数可以通过尽量让中位数落在更大的元素上得到，最小中位数则对应更小的位置。整体思路非常简洁，时间复杂度主要来自排序，为 <code>O(n log n)</code>，适合在线测评快速实现。
