狗狗家阳谷县Onsite

您好！
本帖隐藏的内容需要积分高于 80 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 80 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lllllgggggjksjk 发表于 2018-12-1 00:58
是的呢！！棒棒哒！

还是有点奇怪，首先input了所有k个替换数字的index？除去替换的k个数字，剩下的仍然是sorted，不用分为k个sorted parts？

第一题我之前面TuSimple考过，可以用栈。
依次将每个元素入栈，如果碰到当前元素小于栈顶，则将这两个元素都拿出来放到另一个数组中。
这样你就有了一个排序好的n-2k个元素，和2k个“疑似”被改过的元素。
对2k个元素进行排序，然后对这两个数组进行归并排序。
总时间复杂度klogk + n，因为k很小，所以可以认为是O(n)。

第一题替换的k个index是已知吗？还是需要遍历后再分成k个sorted array？

caitlin 发表于 2018-12-5 17:32
第一题替换的k个index是已知吗？还是需要遍历后再分成k个sorted array？

需要遍历的，紫薯紫薯

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

大木虫 发表于 2018-12-8 01:35
层主的想法解答了我的疑惑，很强！
我想到了归并排序，但是想的是吧被改变的k个挑出来，不知道如何做， ...

谢谢夸奖。
我面TuSimple的时候，这道题我给了一个“标记法”，把所有疑似是被改变的k个元素标记出来。写起来就比较复杂了。。。

请问下楼主， 最后一道题补足了位数后是单独的空间来记录补0 的位数么？

请问高频猜字题是LC哪题呀

请问楼主这个第四题 考察的是什么呀，就把每个字母换成00这种二进制表述然后连起来？还是我哪里没有理解到。。谢谢，已加米！