i**********e
发帖数: 1145 | 1 最近非常热门的一道 google 题，大家讨论讨论.
Two reverse sorted arrays A and B have been given.
such that size of A is m and size of B is n
You need to find the k th largest sum (a+b) where a is taken from A and b is
taken from B. such that k < m*n
本版又讨论过，但是好像没什么结果。
http://www.mitbbs.com/article_t/JobHunting/31684697.html
这题其实可以转换成另外以下的题目（杨式矩阵）：
Given a N*N Matrix.
All rows are sorted, and all columns are sorted.
Find the Kth Largest element of the matrix.
我想到一个利用堆的解法，可以达到 O(k log min(m, n)).
但看网上 google 要求的最优解法好像是 O(n).
不知道各位大侠有没有任何好的思路.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | g*********s
发帖数: 1782 | 2 为什么要reverse sorted?
b is
【在 i**********e 的大作中提到】
: 最近非常热门的一道 google 题，大家讨论讨论.
: Two reverse sorted arrays A and B have been given.
: such that size of A is m and size of B is n
: You need to find the k th largest sum (a+b) where a is taken from A and b is
: taken from B. such that k < m*n
: 本版又讨论过，但是好像没什么结果。
: http://www.mitbbs.com/article_t/JobHunting/31684697.html
: 这题其实可以转换成另外以下的题目（杨式矩阵）：
: Given a N*N Matrix.
: All rows are sorted, and all columns are sorted.
| i**********e
发帖数: 1145 | 3 这是题目愿意呀。
就是 A 和 B sorted in descending order 的意思。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*********s 的大作中提到】
: 为什么要reverse sorted?
:
: b is
| g*********s
发帖数: 1782 | 4 我的意思是说正排序问题应该等价吧。
【在 i**********e 的大作中提到】
: 这是题目愿意呀。
: 就是 A 和 B sorted in descending order 的意思。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 5 哦，原来这个意思。
是的，都一样是等价的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*********s 的大作中提到】
: 我的意思是说正排序问题应该等价吧。
| i**********e
发帖数: 1145 | 6 My solution using a heap and an array that maps indices from A to B.
const int MAX_M = 100;
const int MAX_N = 100;
typedef pair Pair;
int findKthLargestSum(int A[], int m, int B[], int n, int k) {
priority_queue Q;
int AToB[MAX_M] = {0}; // keep track of each col's indices that's
traversed.
// pushes all elements of the first row into heap
for (int i = 0; i < m; i++)
Q.push(Pair(A[i]+B[0], i));
// loop k-1 times to find the first k-1 elements
for (int i = 0; i < k-1; i++) {
Pair largest = Q.top();
Q.pop();
AToB[largest.second]++;
// push its next element in the current col (next row)
if (AToB[largest.second] < n)
Q.push(Pair(A[largest.second]+B[AToB[largest.second]], largest.second));
}
return Q.top().first;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | j*****e
发帖数: 3 | 7 How about trying to find the kth smallest element
in the N*N matrix?
If you draw a line from
A[1, k] to A[k,1] in the matrix, would the kth smallest element sit
somewhere on this line?
For example, will the 4th smallest element will be among
a[4,1], a[3,2], a[2,3], a[1,4]? | i**********e
发帖数: 1145 | 8 To answer your question, No.
Counter example:
A = [9 8 7 6]
B = [9 7 2 1]
9 8 7 1
9 18 17 16 10
7 16 15 14 8
2 11 10 9 3
1 10 9 8 2
The 4th element (16) is not on any of A[4,1], a[3,2], a[2,3], a[1,4].
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | f*******4
发帖数: 1401 | | d*********c
发帖数: 14 | |
|
