两个排序数组A, B，长度为n,m,(n <= m),k,(k >= log n)给定。
用log (nm)可以求出k-th在这两个数组的并集中最小的数。
我有一个解决方案在这里的问题2，但我的挑战是为什么两个给定条件&;(n <= m)&;k>= log n>不影响这个算法吗?
-
第一个假设:
n <= m是一个"不失普遍性"的假设。如果n>= m，那么就在头脑中交换A和B。他们包含了这个假设，即使它是不必要的，因为他们觉得它是"免费的"; -
第二个假设:找到
k第9个最小元素的简单算法是同时遍历A和B，在两个数组中具有较小元素的数组中前进。这将完全类似于运行"合并"。函数，但在合并了前k个元素后停止。复杂度是O(k)他们想让你找到一个更复杂的算法，所以他们排除了通过声明k>= log(n)来实现这个算法，这意味着复杂度O(k)永远不会优于O(log(n))。从技术上讲，如果他们想彻底排除这个算法，他们也应该声明k <= n + m - log(n)，否则你可以运行"合并"。函数:合并n+m-k个最大的元素，然后返回n+m-k中第10个最大的元素，该元素与第k个最小的元素相同。