😇
LeetCode Notebook
  • Introduction
  • Useful Java knowledge
    • Arrays vs Math vs Collections
    • Integer vs int
    • String vs string vs char vs Character
    • StringBuilder vs StringBuffer
    • ArrayList vs Array
    • Stack & Queue
    • HashMap
    • LinkedList
  • Useful Python knowledges
    • Dictionary
    • recursive vs iterative
    • queue 和 stack如何用python实现
    • List, Dictionary, Set 常用的函数
    • Common Mistakes about Python
    • Bit operation
    • sort by second value in Python
    • Initialize list in Python
  • 完全按照九章算法刷的，70道左右
    • I. Binary Search
      • 34.Find First and Last Position of Element in Sorted Array
      • 35. Search Insert Position
      • 74. Search a 2D Matrix
      • 240. Search a 2D Matrix II
      • 278. First Bad Version
      • 162. Find Peak Element
      • 33. Search in Rotated Sorted Array
      • 81. Search in Rotated Sorted Array II
      • 153. Find Minimum in Rotated Sorted Array
      • 154. Find Minimum in Rotated Sorted Array II
    • II. Sorted Array
      • 88. Merge Sorted Array
      • 23. Merge k Sorted Lists
      • 4. Median of Two Sorted Arrays
      • # Recover rotated sorted array
      • 796. Rotate String
      • 26. Remove Duplicates from Sorted Array
      • 80. Remove Duplicates from Sorted Array II
      • 557. Reverse Words in a String III
    • III. Binary Tree
      • 144. Binary Tree Preorder Traversal
      • 94. Binary Tree Inorder Traversal
      • 145. Binary Tree Postorder Traversal
      • 912. Sort an Array
      • 104. Maximum Depth of Binary Tree
      • 110. Balanced Binary Tree
      • 124. Binary Tree Maximum Path Sum
      • 235. Lowest Common Ancestor of a Binary Search Tree
      • 102. Binary Tree Level Order Traversal
      • 107. Binary Tree Level Order Traversal II
      • 103. Binary Tree Zigzag Level Order Traversal
      • 98. Validate Binary Search Tree
      • 701. Insert into a Binary Search Tree
      • 173. Binary Search Tree Iterator
    • IV. Permutations and Subsets
      • 78. Subsets
      • 90. Subsets II
      • 31. Next Permutation
      • 60. Permutation Sequence
      • 51. N-Queens
      • 17. Letter Combinations of a Phone Number
      • 39. Combination Sum
      • 131. Palindrome Partitioning
      • 126. Word Ladder II
      • 127. Word Ladder
    • VI. Linked List
      • 203. Remove Linked List Elements
      • 206. Reverse Linked List
      • 92. Reverse Linked List II
      • 143. Reorder List
      • 148. Sort List
      • 82. Remove Duplicates from Sorted List II
      • 86. Partition List
      • 141. Linked List Cycle
      • 142. Linked List Cycle II
      • 23. Merge k Sorted Lists
      • 138. Copy List with Random Pointer
    • IX. Dynamic Programming
      • 70. Climbing Stairs
      • 120. Triangle
      • 62. Unique Paths
      • 63. Unique Paths II
      • 64. Minimum Path Sum
      • 55. Jump Game
      • 300. Longest Increasing Subsequence
      • 139. Word Break
      • 132. Palindrome Partitioning II
      • 72. Edit Distance
      • 1143. Longest Common Subsequence
      • 97. Interleaving String
      • 115. Distinct Subsequences
  • 开始自己刷，冲刺100道，主要是binarySearch&Tree
    • 981. Time Based Key-Value Store
    • 111. Minimum Depth of Binary Tree
    • 112. Path Sum
    • 113. Path Sum II
    • 100. Same Tree
    • 101. Symmetric Tree
    • 96. Unique Binary Search Trees
    • 108. Convert Sorted Array to Binary Search Tree
    • 226. Invert Binary Tree
    • 95. Unique Binary Search Trees II
    • 50. Pow(x, n)
    • 69. Sqrt(x)
    • 167. Two Sum II - Input array is sorted
    • 29. Divide Two Integers*
    • 349. Intersection of Two Arrays
    • 287. Find the Duplicate Number
    • 222. Count Complete Tree Nodes
    • 350. Intersection of Two Arrays II
    • 257. Binary Tree Paths
    • 404. Sum of Left Leaves
    • 437. Path Sum III
    • 7. Reverse Integer
    • 21. Merge Two Sorted Lists
    • 279. Perfect Squares
    • 199. Binary Tree Right Side View
    • 114. Flatten Binary Tree to Linked List
    • 129. Sum Root to Leaf Numbers
    • 198. House Robber
    • 213. House Robber II
    • 337. House Robber III
    • 236. Lowest Common Ancestor of a Binary Tree
  • 终于刷到100道了，我是分水岭，开始按照网上推荐重点250道题
    • 补充1-20道
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 9. Palindrome Number
      • 11. Container With Most Water
      • 12. Integer to Roman
      • 13. Roman to Integer
      • 15. 3Sum
      • 18. 4Sum
      • 20. Valid Parentheses
      • 22. Generate Parentheses
      • 27. Remove Element
      • 28. Implement strStr()
      • 31. Next Permutation
      • 36. Valid Sudoku
      • 38. Count and Say
      • 40. Combination Sum II
      • 41. First Missing Positive
      • 43. Multiply Strings
      • 48. Rotate Image
      • 49. Group Anagrams
  • 补充21-40道
    • 53. Maximum Subarray
    • 66. Plus One
    • 67. Add Binary
    • 71. Simplify Path
    • 75. Sort Colors
    • 77. Combinations
    • 79. Word Search
    • 91. Decode Ways
    • 116. Populating Next Right Pointers in Each Node
    • 117. Populating Next Right Pointers in Each Node II
    • 121. Best Time to Buy and Sell Stock
    • 122. Best Time to Buy and Sell Stock II
    • 125. Valid Palindrome
    • 133. Clone Graph
    • 134. Gas Station
    • 146. LRU Cache
    • 150. Evaluate Reverse Polish Notation
    • 152. Maximum Product Subarray
    • 155. Min Stack
    • 157. Read N Characters Given Read4
  • 补充41-60道
    • 160. One Edit Distance
    • 163. Missing Ranges
    • 168. Excel Sheet Column Title
    • 169. Majority Element(位运算)
    • 170. Two Sum III - Data structure design
    • 171. Excel Sheet Column Number
    • 175. Combine Two Tables(SQL)
    • 176. Second Highest Salary(SQL)
    • 177. Nth Highest Salary(SQL)
    • 178. Rank Scores(SQL)
    • 180. Consecutive Numbers(SQL)
    • 181. Employees Earning More Than Their Managers(SQL)
    • 182. Duplicate Emails(SQL)
    • 183. Customers Who Never Order(SQL)
    • 184. Department Highest Salary(SQL)
    • 185. Department Top Three Salaries(SQL)
    • 57. Insert Interval
    • 355. Design Twitter
    • 328. Odd Even Linked List(经典)
  • 补充61-80道
    • 378. Kth Smallest Element in a Sorted Matrix
    • 309. Best Time to Buy and Sell Stock with Cooldown
    • 186. Reverse Words in a String II
    • 190. Reverse Bits(bit)
    • 191. Number of 1 Bits(bit)
    • 196. Delete Duplicate Emails（SQL）
    • 197. Rising Temperature(SQL)
    • 200. Number of Islands
    • 201. Bitwise AND of Numbers Range
    • 202. Happy Number
    • 204. Count Primes
    • 205. Isomorphic Strings
    • 208. Implement Trie (Prefix Tree)
    • 211. Design Add and Search Words Data Structure
    • 215. Kth Largest Element in an Array
    • 216. Combination Sum III
    • 217. Contains Duplicate
    • 219. Contains Duplicate II
    • 220. Contains Duplicate III
    • 225. Implement Stack using Queues
  • 补充81-100道
    • 2. Add Two Numbers
    • 19. Remove Nth Node From End of List
    • 227. Basic Calculator II
    • 228. Summary Ranges
    • 231. Power of Two
    • 232. Implement Queue using Stacks
    • 234. Palindrome Linked List
    • 237. Delete Node in a Linked List
    • 242. Valid Anagram
    • 258. Add Digits
    • 263. Ugly Number
    • 268. Missing Number
    • 283. Move Zeroes
    • 290. Word Pattern
    • 303. Range Sum Query - Immutable
    • 26. Power of Three
    • 342. Power of Four
    • 344. Reverse String
    • 655. Print Binary Tree
    • 224. Basic Calculator
Powered by GitBook
On this page
  • Solution 1:
  • Solution 2:

Was this helpful?

  1. 完全按照九章算法刷的，70道左右
  2. II. Sorted Array

4. Median of Two Sorted Arrays

# Hard

Previous23. Merge k Sorted ListsNext# Recover rotated sorted array

Last updated 4 years ago

Was this helpful?

Solution 1:

Compare the len(nums1)/2th and len(nums2)/2th element, increase or decrease the position based on different situations. Very hard. Give up temporary. Time complexity is O(lg(min(m,n)))O(lg(min(m,n)))O(lg(min(m,n)))

Solution 2:

Think about it as finding the kth element in two sorted array. Compare thek/2th element in nums1 and k/2th element in nums2, then throw k/2 element. This algorithm uses iteration with binary search. Its time complexity is O(lgk)O(lgk)O(lgk)

Detail explanation tutorial