← 返回 apple 的题目列表Top K Closest Pairs in a Sorted Array
类型：online_judge
Given a non-decreasing sorted integer array nums and an integer k, return the k pairs with the smallest distances among all index pairs (i, j) where 0 <= i < j < n.
The distance is:
distance(i, j) = |nums[i] - nums[j]|
Because the array is sorted, for i < j, the distance is nums[j] - nums[i].
Return k value pairs (nums[i], nums[j]), ordered by:
Increasing distance;
For equal distances, increasing left index i;
If left indices are also equal, increasing right index j.
k does not exceed the total number of pairs, n * (n - 1) / 2.
Input Format
n k
nums[0] nums[1] ... nums[n-1]
Output Format
Print one pair per line:
left right
Example
Input:
6 2
1 2 4 7 11 16
Output:
1 2
2 4
Example
Input
6 2
1 2 4 7 11 16
Output
1 2
2 4