小金人 new grad OA

coding 一道是Mean

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

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

大家都有好运！

JanzenLiu 发表于 2020-7-24 07:04
请问楼主是 New Analyst 岗嘛？

是的！【八个字好难

请问楼主是 New Analyst 岗嘛？

请问Meandering array是哪道题呀，感谢感谢！！

统计统计！！！ 发表于 2020-7-24 13:19
请问Meandering array是哪道题呀，感谢感谢！！

就是这道题！主楼好像不能编辑555

感谢楼主分享！请问meandering array这道题有空间限制吗？直接开辟一个新的array return吗？那不是sort一下就解决了？？

        很有用的信息！

感谢楼主， 请问您是网投吗 还是有人内推呢

同问 第二题有空间限制马。

meandering array如何用O(1)空间复杂度完成：
Two pointers一个maxIndex从右往左，一个minIndex从左往右，相向而行
设置maxElement = 初始array中最大的element + 1，这样做保证整个array里任何一个element % maxElement = element本身
然后就简单了
Case 1 (Even Index): arr[i] = arr[i] + arr[maxIndex--] % maxElement * maxElement
Case 2 (Odd Index): arr[i] = arr[i] + arr[maxIndex--] % maxElement * maxElement

这里我们用了multiplication and modular trick来使得一个index可以store两个element，i.e.那个index初始情况的数字&后来填进去的数字。

初始情况的数字可以用arr[i] % maxElement来获得
证明：(arr[i] + arr[maxIndex] % maxElement * maxElement) % maxElement = arr[i] + 0 (数学逻辑自己去推导，注意java运算规律)

后来填进去的数字可以用arr[i] / maxElement来获得
证明：(arr[i] + arr[maxIndex] % maxElement * maxElement) / maxElement = arr[maxIndex] % maxElement (数学逻辑自己去推导，注意java运算规律)

这样用一个for loop走过一边以后就可以用再用一个for loop，从头到尾arr[i] / maxElement来获得最终答案了。

reference: https://www.geeksforgeeks.org/re ... t-2-o1-extra-space/