非斯不可实习vo

店面

1. remove 0 in LinkedList
2. 2d array， col 是 independently sorted， row 不是，找kth 小的数

第二个脑子完全没有转出来 一直不自觉在想column之间有联系但其实没有 归根结底还是太菜了想问大家fb的冷冻期是从收到拒信那天开始算起吗

第二题可以先把每个col第一个元素加到mean heap里面，然后pop最小的，check最小的是哪个col的，就把那个col的下一个元素再加进来。直到pop到了第k个。这样应该是O(klogn) ,假设有n个col。

第二题能不能traverse每一个row然后每一个row里用binary search呢

第二题方法可以仿照Leetcode 378的heap吗，感觉题意有点相似

【deleted】

请问 第二题 row 是 完全随机的嘛。谢谢！

还有就是第一题只是相当于 delete target node 嘛， 已加米

lazysheep123 发表于 2020-11-05 17:18:15
还有就是第一题只是相当于 delete target node 嘛， 已加米

对 比如说 1 -> 0-> 2 -> 3-> 0 -> 0 return 1 -> 2 -> 3

lazysheep123 发表于 2020-11-05 17:12:52
请问 第二题 row 是 完全随机的嘛。谢谢！

是的 row随机 columns independently sorted

走地蒲公英 发表于 2020-11-06 07:34:47
第二题能不能traverse每一个row然后每一个row里用binary search呢

如果我没有理解错你是觉得第k个数=k吗？我感觉binary search不行主要是我们不知道target数字是哪个因为数字可以duplicate.. 我现在想可以用一个k sized 的 max heap，然后每个column一直往里面塞，每个column塞的终止条件是 pop出来的数=塞进去的数，最后每个column都看过了peek的就是第k小的

先找最大和最小值，然后取mean，然后扫每个col，找比mean小的。如果比K大update max to mean，比K小update min=mean。比较奇葩的二分法。https://www.geeksforgeeks.org/find-median-row-wise-sorted-matrix/