滴滴SP专场面试
求助这个题:一个数组，0<=ai<=n-1 有些数字是出现2次，有些数字出现1次，要求时间复杂度是On 空间复杂度是O1，找出出现2次的数字。
刚开始我说的是hashmap，但是没面试管说必须空间复杂度是O1 ，求助道友！我找了leetcode所有的出现次数的题目， 也不是原题。
#滴滴##内推##笔试题目##面经#
2020-07-26 20:26 已编辑 阿里巴巴_淘天_后端工程师
关注
全部评论
一个菜鸡的自我修养
西北工业大学 研发工程师
嘿楼主，可以考虑类似于利用数组下标原地排序，大致思想就是把每个元素放到下标序号与其值相等的位置，重复的元素必然其原位置已经存在值相同的元素，记录下该元素及当前已出现的次数，从前到后扫描整个数组，最后输出重复次数为2 的元素
colors_clor
哈尔滨工业大学 算法工程师
允许修改数组的话，然后套leetcode442的做法。第一次扫描，将没有出现的置负，第二次扫描，每个数字置负——由此，出现一次和没有出现的位置是负，出现两次的，负负得正。 [4,3,2,7,8,2,3,1] 全负---> [-4,-3,-2,-7,-8,-2,-3,-1] 将出现过的置为正---> [4,3,2,7,-8,-2,3,1] 将nums[nums[i]]反转---> [-4,3,2,-7,-8,-2,-3,-1] 找为正的位置 [2,3]
全村人的希望201907161411392
快手_测试开发工程师
题目给了范围，所以可以把数字映射到下标。
狗傻
门头沟学院 算法工程师
允许改变原数组的前提下可以考虑相反数
杨之光
中国科学院大学 C++
leetcode442…这不是经典题吗
美女bug制造机
门头沟学院 测试工程师
请问在哪里投递呢，有链接吗，找了好久也没找到🤨
offer速来哈
西安邮电大学 运维工程师
请问楼主在哪里投的呀 现在还可以投嘛
改个名字好难啊啊啊啊
字节跳动_AI LAB_计算机视觉
求和－等差数列和
messi399
华东理工大学 Java
和数组找最小正数那题一样，参考10楼思路
iBond
西安电子科技大学 Java
剑指offer50？
000201812191127695
沈阳工业大学 Java
LeetCode136是用的亦或，LeetCode442是用的原地操作
敛先生
蚂蚁集团_测试开发工程师
这不是原题嘛，原地移动啊，可以不用额外的空间。 还有同类题目是找出没有出现的数字🤣 楼主你再刷刷吧
json_z
华南农业大学 C++
m
colors_clor
哈尔滨工业大学 算法工程师
0<=ai<=n-1，n是什么，数组长度为n？
延陵不折柳
门头沟学院 算法工程师
这不是经典异或题吗
相关推荐