Snap 电面

hongelee

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 hongelee 于 2020-2-29 04:12 编辑

Shuffle Object
给一个array of object，要求梅花间隔shuffle，要求in plac

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

把object 逐个左移到目标位置。O(n^2)

就这一题想不到更优解卡住了，知道更优解可以告诉我一下。

求大米，面筋都看不了 T_T ～

knightna

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

ttwjytt

sort+双指针+swap-O（logN）

补充内容 (2020-3-7 18:13):
O（nlogn）

derekdomo

hongelee 发表于 2020-2-29 06:10
在第一次swap之前是可以知道每个object应该在哪个位置的，但是之后就乱了呀。又不能allocate extra space ...

https://www.geeksforgeeks.org/sh ... -using-extra-space/
可以看看这个，应该是和你说的是一个题

SophieJ

多快给的结果

hongelee

SophieJ 发表于 2020-2-29 03:56
多快给的结果

第二天紫薯紫薯紫薯

hongelee

知道更优解的可以告诉我一下

SophieJ

先sort一下，把数字和字母分成两边，在头尾两个指针swap? O(nlogn)了。

hongelee

SophieJ 发表于 2020-2-29 04:53
先sort一下，把数字和字母分成两边，在头尾两个指针swap? O(nlogn)了。

是object，不一定是字母或者数字，所以也没大小可言

derekdomo

有点像cyclic sort，根据index可以推算出应该在的位置，这样循环的replace感觉应该就可以一次替换完所有了

hongelee

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

hongelee

knightna 发表于 2020-2-29 06:55
Naive的方法就相当于插入排序。选择a，插入2的位置。。。 N*N

思路不错，但是要是个数是奇数，要把median平移到最后，不是要和右边挨个swap么，复杂度不也是O（N*N）？