공부한 것
- LeetCode #295. Find Median from Data StreamFind Median from Data Stream - LeetCodeCan you solve this real interview question? Find Median from Data Stream - The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. * For example, for arr = [2,3,4], the median is 3. * For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5. Implement the MedianFinder class: * MedianFinder() initializes the MedianFinder object. * void addNum(int num) adds the integer num from the data stream to the data structure. * double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted. Example 1: Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0 Constraints: * -105 <= num <= 105 * There will be at least one element in the data structure before calling findMedian. * At most 5 * 104 calls will be made to addNum and findMedian. Follow up: * If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? * If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
https://leetcode.com/problems/find-median-from-data-stream/
⇒ 난이도 Hard여서 그런지, 이진 탐색 트리 구현 후 중위 순회로 중위값을 찾는 전략이 실행 시간 초과로 실패했다.
시간 복잡도 구해보기:
두 메소드 중 addNum()은 시간복잡도가 O(log(N!)), findMedium은 O(N/2)이다. log(N!)은 대략 Nlog(N)으로 볼 수 있으므로 전체 시간 복잡도는 O(Nlog(N))으로 볼 수 있다.
시간 복잡도 시나리오 1: addNum()을 5만 번 호출 후 findMedium()을 1번 호출 시나리오 2: addNum()을 1번 호출하고 findMedium()을 5만 번 호출 전략1: 이진 탐색 트리 구축 후 중위 순회 O(N log(N) + N/2) O(log(N) + N(N/2)) = O(N^2) 전략2: findMedium()에서 sort() 이용 O(N log(N)) O(N + ?)
풀이 코드:
class TreeNode { val: number left: TreeNode | null right: TreeNode | null constructor(value: number) { this.val = value; this.left = null; this.right = null; } } class BinarySearchTree { root: TreeNode | null; length: number; constructor() { this.root = null; this.length = 0; } // 이진 탐색 트리에 새로운 노드를 삽입 insert(value: number): void { const node = new TreeNode(value); if (!this.root) this.root = node; else this.insertNode(this.root, node); this.length++; } // 재귀적으로 노드를 삽입하는 도우미 함수 private insertNode(node: TreeNode, newNode: TreeNode): void { // 새로운 노드가 지금 살피는 노드보다 작으면 지금 노드의 왼 자식을 채우고, 왼 자식이 이미 차 있다면 그 왼 자식에 대해 다시 재귀호출해서 알맞은 자리를 탐색한다. if (newNode.val < node.val) { if (!node.left) node.left = newNode; else this.insertNode(node.left, newNode); } else { if (!node.right) node.right = newNode; else this.insertNode(node.right, newNode); } } } class MedianFinder { private tree: BinarySearchTree; constructor() { this.tree = new BinarySearchTree(); } addNum(num: number): void { this.tree.insert(num); } findMedian(): number { // 이진 탐색 트리를 중위순회하다가 result에 담긴 개수가 반절이 되는 순간 마지막 result 요소를 반환하기. // 전체 개수가 홀수일 때: i=(전체 개수 / 2)내림. => result 배열 길이가 i+1개가 되었을 때 result[i]를 반환한다. // 전체 개수가 짝수일 때: i= (전체 개수 / 2 - 1), i+1 = 전체 개수 / 2. => result 배열 길이가 i+2개가 되었을 때 result[i]+result[i+1]를 2로 나눈 값을 반환한다. // if (!this.tree) return 0; const resultMap: Map<TreeNode, number> = new Map(); const stack: TreeNode[] = [this.tree.root]; while (stack.length) { const node = stack[stack.length - 1]; if (node.left && !resultMap.has(node.left)) { stack.push(node.left); } else { resultMap.set(node, node.val); // 전체 5개 => 3개가 찼을 때 멈춤 // 전체 6개 => 4개가 찼을 때 멈춤 // = 전체 / 2를 내림하고 +1한 값 const stopMoment = Math.floor(this.tree.length / 2) + 1 if (resultMap.size === stopMoment) { const result = [...resultMap.values()]; if (this.tree.length % 2 === 1) return result[stopMoment - 1]; else return (result[stopMoment - 2] + result[stopMoment - 1]) / 2; } stack.pop(); node.right && stack.push(node.right); } } } }
Uploaded by N2T