[LeetCode] Median of Two Sorted Arrays
leetcode.com/problems/median-of-two-sorted-arrays/submissions/
Median of Two Sorted Arrays - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
2021-01-01
|
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
import java.util.Arrays;
import java.util.PriorityQueue;
public class SolutionMedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
double result = 0;
int len = nums1.length+nums2.length;
int x = 0;
int y = 0;
int idx = 0;
int prev = 0;
int cur = 0;
while(x < nums1.length || y < nums2.length) { // 71.33%
if(x < nums1.length && y < nums2.length) {
if(nums1[x] < nums2[y]) {
cur = nums1[x];
x++;
} else {
cur = nums2[y];
y++;
}
} else if(x < nums1.length && y >= nums2.length) {
cur = nums1[x];
x++;
} else if(x >= nums1.length && y < nums2.length) {
cur = nums2[y];
y++;
}
if(idx == len/2) break;
idx++;
prev = cur;
}
if(len % 2 == 0) result = (prev+cur) / 2.0;
else result = cur;
// (2) using array
int merge[] = new int[len];
while(x < nums1.length || y < nums2.length) { // 57.55%
if(x < nums1.length && y < nums2.length) {
if(nums1[x] < nums2[y]) {
merge[idx] = nums1[x];
x++;
} else {
merge[idx] = nums2[y];
y++;
}
} else if(x < nums1.length && y >= nums2.length) {
merge[idx] = nums1[x];
x++;
} else if(x >= nums1.length && y < nums2.length) {
merge[idx] = nums2[y];
y++;
}
if(idx == len/2) break;
idx++;
}
if(len % 2 == 0) {
result = (merge[len/2] + merge[len/2-1]) / 2.0;
} else result = merge[len/2];
// (3) using priorityqueue
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i = 0; i < nums1.length; i++) q.add(nums1[i]);
for(int i = 0; i < nums2.length; i++) q.add(nums2[i]);
for(int i = 0; i < len; i++) {
merge[i] = q.poll();
}
if(len % 2 == 0) {
result = (merge[len/2] + merge[len/2-1]) / 2.0;
} else result = merge[len/2];
return result;
}
public static void main(String[] args) {
int n[] = {1,2};
int n2[] = {3,4};
System.out.println(findMedianSortedArrays(n, n2));
}
}
|
cs |
#문제풀이
(3) 맨 처음에는 priorityqueue로 풀었다. 단순하게 priorityqueue에 두 개의 배열 값을 넣었고, 알맞는 중간값을 출력했다. 간단하고 편한 방법이긴 하지만 시간이 너무 오래걸렸다.
(2) 두 번째로는 새로운 merge 배열을 만들어서 두 개의 배열을 하나로 합쳤다. 두 개의 배열을 탐색하면서 새로운 배열을 만드는 로직으로 짰다. 각각의 배열을 위한 인덱스 변수 x, y 를 선언하고, x,y 인덱스 값에 따라 조건을 주어서 순서에 맞게 merge array를 만들었다.
(1) 그런데 메모리 사용률이 좀 높아서 배열을 빼고 단순히 변수로 계산을 했다. cur와 prev 변수를 만들어서, cur는 현재 index에 해당하는 값, prev는 그 전 값을 저장했다. prev를 사용하는 이유는 두 배열의 길이의 합이 짝수인 경우 (cur + prev) / 2.0으로 계산해야 되기 때문이다.
+) 마지막 방법으로 하면 다음과 같은 결과를 얻을 수 있다.
Runtime: 2 ms, faster than 99.71% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 71.33% of Java online submissions for Median of Two Sorted Arrays.