狗家店面

第二轮电话面试是国人小哥哥
给一个排序好的int数组，修改其中某些元素
让我处理修改过后的数组，使得这个数组依旧是排序好的数组。

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

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

smilieid="112" border="0" alt="" />

loop一遍取出排序不对的数 O(n), 并且把原数组剩余的element都往前移
对取出的数据排序O(klogk)
然后合并两个数组都原数组中 O(n)

两个方法
求大米

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

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

最坏的情况，比如说 [1,2,3,4,5] 变成了[5,4,3,2,1]的时候, 这个时候 k == n, 时间消耗应该不会小于O(nlogn)
用PiorityQueue(heap)的情况下，由于所有数字要重新插入，每个数字插入消耗 O(logn), 全部插入一次就是 O(nlogn)了.
请问到底要如何优于O(nlogn)?

感謝LZ分享~!

楼主请问修改某些元素是可能修改所有的元素吗？

s961206 发表于 2018-11-20 02:54
感謝LZ分享~!

那能不能厚颜无耻的请求一些大米啊

516364598chang 发表于 2018-11-20 03:05
楼主请问修改某些元素是可能修改所有的元素吗？

有可能的，任意位置的任意多个元素，我们不知道修改了哪几个，但是会告诉我们总共修改了几个。

想问一下是交换了其中几个元素？还是修改成任意数？请问楼主是怎么做的？已加分

516364598chang 发表于 2018-11-20 03:17
想问一下是交换了其中几个元素？还是修改成任意数？请问楼主是怎么做的？已加分

修改成任意数都可能。我是把不符合升序规则的数字找出来，然后开了空间，重新插值到数组里面。

Yingguo 发表于 2018-11-20 03:19
修改成任意数都可能。我是把不符合升序规则的数字找出来，然后开了空间，重新插值到数组里面。

比如 [1, 2, 3, 4, 5, 6, 7, 8] -> [1， -1， 3， -4， 5， 8，7， 8],
是怎么分呢？

516364598chang 发表于 2018-11-20 03:38
比如 [1, 2, 3, 4, 5, 6, 7, 8] -> [1， -1， 3， -4， 5， 8，7， 8],
是怎么分呢？

就对比大小

请问楼主是用找出来的数， 然后对之前排序好的数组进行二分查找，找到插入index再加进去吗？