[Letcode/4]二次シードアレイ(Hard,Java)Median of
Question問題リンク:https://leetcode.com/problems/median-of-two-sorted-arrays/2 分類:優先キュー 解答時間:10分 問題の説明サイズnのnum 1とサイズmのnum 2の配列 この2つの配列の中央値を求めます がちょうどずれている中心値がない場合(=2つの配列の長さは偶数)、中心に近い両端値を返す平均値は である.
時間複雑度O(対数(n+m)O(対数(n+m)O(対数(n+m) )
Solution
プールアクセス方法は、2つの優先キューでソートされます. 中央、小値優先キュー:降順配列 中央キュー、大値キュー:昇順 の2つの優先順位キューの上部の値は、中心値 を自動的に表す.
正しいコード
Solution
プールアクセス方法
正しいコード
import java.util.*;
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>(Collections.reverseOrder());
PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>();
for (int i = 0; i < nums1.length; i++) {
// 큐에 들어가 있는 숫자의 개수에 따라 번갈아서 넣어 줌
if (maxQueue.size() < minQueue.size()) {
maxQueue.add(nums1[i]);
} else {
minQueue.add(nums1[i]);
}
if (!minQueue.isEmpty() && !maxQueue.isEmpty()) {
// 큰 값이 들어가있는 큐의 제일 작은 값이, 작은 값이 들어가있는 큐의 제일 큰 값보다 작을 경우
// 둘을 바꿔서 넣어줌
if (minQueue.peek() > maxQueue.peek()) {
int temp = minQueue.poll();
minQueue.add(maxQueue.poll());
maxQueue.add(temp);
}
}
}
for (int i = 0; i < nums2.length; i++) {
if (maxQueue.size() < minQueue.size()) {
maxQueue.add(nums2[i]);
} else {
minQueue.add(nums2[i]);
}
if (!minQueue.isEmpty() && !maxQueue.isEmpty()) {
if (minQueue.peek() > maxQueue.peek()) {
int temp = minQueue.poll();
minQueue.add(maxQueue.poll());
maxQueue.add(temp);
}
}
}
// 딱 떨어지는 중앙값 없으면, 양 옆 숫자의 평균 리턴
if(maxQueue.size() == minQueue.size()) {
return (maxQueue.poll() + minQueue.poll()) / 2.0;
} else if (maxQueue.size() > minQueue.size()) {
return (double) maxQueue.poll();
} else {
return (double) minQueue.poll();
}
}
}Reference
この問題について([Letcode/4]二次シードアレイ(Hard,Java)Median of), 我々は、より多くの情報をここで見つけました https://velog.io/@hyunjkluz/Leetcode릿코드4-Median-of-Two-Sorted-Arrays-Hard-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol