中级农民
- 积分
- 132
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-2-17
- 最后登录
- 1970-1-1
|
本帖最后由 newgod2500 于 2017-6-25 02:19 编辑
比较暴力,General(如果数组无序)一点的思路是建一个minHeap, 把N个元素塞进去,然后按k取值,这样时间复杂度是O(N+k),空间要求是O(N); 不太符合题意 (当然把N个元素重新sort,就更暴力了)
既然我们知道了M, N和K的话, N是个很大的数字,意味着N/M 也是个大数,我们的思路最好不要跟N挂上钩。
每个数组都是有序的(假设是升序,降序的话方向需要反过来;无论如何变化都是从M个数组里,每个数组的最小数开始),我们改进一下思路。
首先建一个priority queue, 然后把M个数组的第一个元素Enqueue进去。大概思路跟LeetCode 上 378很像。不过378的输入是个matrix, 这里是个 jagged array-like的输入。
然后根据k来写一个while循环,做k次操作,每次只对priority queue的头一个元素, 头元素是largest element in the pq进行操作,下面的代码可能有Bug,我没检查,但大概思路是正确的:
while(K > 0)
{
start = pq.First();
int x = pq.First().Item1; // index among in the M arrays
int y = pq.First().Item2; // index in the M[x] array
pq.RemoveAt(0); //Remove the first
if(y < M[x].Length - 1)
{
pq.Insert(M[x][y+1]);
}
k--;
}
return start;
因为C#里没有pq, 只有SortedDictionary 和SortedList, 如果K很大的话(此处是N/3,优先考虑SortedDicitonary来满足最快的插入和删除performance =>都是O(logN))
时间复杂度是O(M*logK + k) , 空间上因为我们一直维持着一个size 为M 的优先队列,可以认为是O(M)
在大部分情况下, 是比O(M*logN)是要快一点的。不知道我的方法是否符合要求。
Updated:
经朋友提醒,时间复杂度应该是
M个数组第一项建堆 是O(M*logM), 然后取k次最小值是 K*logM 所以总的应该是 O(K*logM), 考虑到k可能会很大 所以应该是趋近于O(N*logM)
|
|