Given two integer arrays sorted in ascending order and an integer k. Definesum = a + b, where_a_is an element from the first array and_b_is an element from the second one. Find the_k_th smallest sum out of all possible sums.
Have you met this question in a real interview?
Yes
Example
Given[1, 7, 11]
and[2, 4, 6]
.
For k =3
, return7
.
For k =4
, return9
.
For k =8
, return15
.
Do it in either of the following time complexity:
- O(k log min(n, m, k)). where n is the size of A, and m is the size of B.
- O( (m + n) log maxValue). where maxValue is the max number in A and B.
line 51 has to use const Node
&
other const
line 21 forgotten , usual errors
class Solution {
public:
/\*\*
\* @param A an integer arrays sorted in ascending order
\* @param B an integer arrays sorted in ascending order
\* @param k an integer
\* @return an integer
\*/
int kthSmallestSum\(vector<int>& A, vector<int>& B, int k\) {
// Write your code here
if \(A.empty\(\)\) {
return B\[k - 1\];
}
if \(B.empty\(\)\) {
return A\[k - 1\];
}
vector<vector<bool> > used\(A.size\(\), vector<bool>\(B.size\(\), false\)\);
priority\_queue<Node> heap;
Node node\(0, 0, A\[0\] + B\[0\]\);
used\[0\]\[0\] = true;
heap.push\(node\);
vector<vector<int> > dirs = { {1,0}, {0,1}};
for \(int i = 0; i < k; ++i\) {
if \(heap.empty\(\)\) {
return -1;
}
auto node = heap.top\(\); heap.pop\(\);
if \(i == k - 1\) {
return node.val;
}
for \(auto& dir : dirs\) {
int nx = node.x + dir\[0\];
int ny = node.y + dir\[1\];
if \(nx >= A.size\(\) \|\| ny >= B.size\(\) \|\| used\[nx\]\[ny\]\) {
continue;
}
Node newNode\(nx, ny, A\[nx\] + B\[ny\]\);
used\[nx\]\[ny\] = true;
heap.push\(newNode\);
}
}
return -1;
}
private:
struct Node {
Node\(int \_x, int \_y, int \_val\) :
x\(\_x\), y\(\_y\), val\(\_val\) {}
bool operator < \(const Node& other\) const {
return val > other.val;
}
int x, y, val;
};
};