Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements. Thanks to an anonymous reader who posted this question. I would have to admit that this problem is pretty tricky to solve. Like most difficult problems, it requires some pretty clever observations to solve in a neat way. The trivial way, O(m+n): Merge both arrays and the k-th smallest element could be accessed directly. Merging would require extra space of O(m+n). The linear run time is pretty good,
Read full article from Find the k-th Smallest Element in the Union of Two Sorted Arrays | LeetCode
No comments:
Post a Comment