狗家店面

LebronRice 发表于 2018-11-20 09:10
请问楼主是用找出来的数， 然后对之前排序好的数组进行二分查找，找到插入index再加进去吗？

我是每个元素都检查了诶

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

请问这样复杂度会优于nlogn吗?
复杂度这样是多少?

reliveinfire 发表于 2018-11-20 11:27
请问这样复杂度会优于nlogn吗?
复杂度这样是多少?

我感觉最差还是nlogn

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

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

loop一遍取出排序不对的数 O(n)
建个堆 对排序不对的k个数排序 O(klogk)
插入原数组O(klogn)
。。。
不知道对不对，有谁知道O(n)的解法？如果说题干里的误操作是一些swap的话，可以用Hashmap+双指针

以加米~ 问一下楼主如果假设原数组是 0，1，2，3，4，5，6修改成 1000，1，2，3，4，5，6 那应该怎么做？这个体需要找最长的递增序列吗 还是碰到 后面一位比前面小的就提出来？

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

没懂啊楼主，原来的数组还保持吗？插值的时候可以用二分，但是知道空在哪了之后不一定有空在那里啊，还得把所有元素往后移动

补充内容 (2018-11-20 07:09):
O(n)找出不对的数，O(klgk)把选出来的数排个序，然后O(n)双指针merge sort?这样是由O(n)和O(klogk)哪个大决定的，那最差还是nlogn啊

tjuwdz95 发表于 2018-11-20 23:06
没懂啊楼主，原来的数组还保持吗？插值的时候可以用二分，但是知道空在哪了之后不一定有空在那里啊，还得把 ...

确定 大佬有啥O（N）的解法吗

两个方法
求大米

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

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