FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/Week_03/id_140/Leetcode_373_140.java at master · augfool/algorithm · GitHub
augfool
/
algorithm
Public
forked from
algorithm001/algorithm
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
Week_03
/
id_140
/
Leetcode_373_140.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
61 lines (52 loc) · 1.81 KB
Breadcrumbs
algorithm
/
Week_03
/
id_140
/
Leetcode_373_140.java
Copy path
File metadata and controls
61 lines (52 loc) · 1.81 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
import
java
.
util
.*;
/**
* You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
*
* Define a pair (u,v) which consists of one element from the first array and one element from the second array.
*
* Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
*
* Example 1:
*
* Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
* Output: [[1,2],[1,4],[1,6]]
* Explanation: The first 3 pairs are returned from the sequence:
* [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
* Example 2:
*
* Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
* Output: [1,1],[1,1]
* Explanation: The first 2 pairs are returned from the sequence:
* [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
* Example 3:
*
* Input: nums1 = [1,2], nums2 = [3], k = 3
* Output: [1,3],[2,3]
* Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
*/
public
class
Leetcode_373_140
{
public
List
<
int
[]>
kSmallestPairs
(
int
[]
nums1
,
int
[]
nums2
,
int
k
) {
Queue
<
int
[]>
maxHeap
=
new
PriorityQueue
<>(
k
, (
a
,
b
) -> (
b
[
0
] +
b
[
1
] -
a
[
0
] -
a
[
1
]));
for
(
int
num1
:
nums1
) {
for
(
int
num2
:
nums2
) {
int
[]
a
=
new
int
[] {
num1
,
num2
};
int
sum
=
num1
+
num2
;
if
(
maxHeap
.
size
() >=
k
) {
int
[]
max
=
maxHeap
.
peek
();
if
(
sum
<
max
[
0
] +
max
[
1
]) {
maxHeap
.
poll
();
maxHeap
.
offer
(
a
);
}
}
else
{
maxHeap
.
offer
(
a
);
}
}
}
List
<
int
[]>
ans
=
new
LinkedList
<>();
while
(!
maxHeap
.
isEmpty
()) {
ans
.
add
(
maxHeap
.
poll
());
}
Collections
.
reverse
(
ans
);
return
ans
;
}
}
Back
|
FazBrowse Home
|
New Git URL