关注
第二题感觉本质就是让一个数组能够存储两种信息,一个是当前index这个数字出现的个数,另一个就是要确认这个index上的数字是否在正确的位置上。
方法一可以参考leetcode 41,吧当前index上的数字和他应该属于的index上面的数字进行交换, 比如a[10]上面放了11就不需要移动,放了8的话就把8和a[7]上面的数字进行交换。而当交换成功之后为了标记当前位置即a[7]上面的数字已经到了正确位置,则可以采取前面楼层的做法,比如把这个数字置为负数比如-1,然后每次有数字移动到这个index7上的时候,-1减一,最后当前index+1这个数字出现的次数就是此位置负数变正再减一。
方法二就是如果这数组的数字比较小的话,当前位置这个数字是一个interger,有32位,可以用前16位去存当前index+1这个数字的出现的次数。这就有点取巧了。
总之这题主要就是通过用一个数组存储两种信息,不管是用正负来代替boolean,还是用interger或者long多出来的位数存储,核心就是如何用一个数组存2N的信息。
查看原帖
3 1
相关推荐
点赞 评论 收藏
分享
04-14 14:42
西北大学 产品经理 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 我的实习收获 #
31938次浏览 504人参与
# 我的租房踩坑经历 #
30023次浏览 292人参与
# 实习吐槽大会 #
34453次浏览 161人参与
# 2025牛客秋招季 #
5056次浏览 157人参与
# 晒一晒你的工位 #
86301次浏览 307人参与
# 穿越回高考你还会选现在的专业吗 #
22708次浏览 268人参与
# 26届秋招投递记录 #
4214次浏览 113人参与
# 双非能在秋招上岸吗? #
215308次浏览 1144人参与
# 毕业旅行去哪玩儿 #
1312次浏览 33人参与
# 移动求职进展汇总 #
1576次浏览 17人参与
# 如果有时光机,你最想去到哪个年纪? #
47233次浏览 800人参与
# 非技术岗简历怎么写 #
209873次浏览 2861人参与
# 求职遇到的搞笑事件 #
113137次浏览 768人参与
# 打工人锐评公司红黑榜 #
146170次浏览 920人参与
# 找工作有哪些冷知识 #
97881次浏览 1380人参与
# 携程求职进展汇总 #
533418次浏览 3989人参与
# 商战,最累的是我们 #
13140次浏览 52人参与
# 我和mentor的爱恨情仇 #
44102次浏览 279人参与
# 第一份工作应该选高薪还是热爱? #
61633次浏览 561人参与
# 大疆工作体验 #
11513次浏览 73人参与