输入:给定n个元素的数组,其中包含从0到n-1的元素,这些数字中的任何一个都会出现任意次数.
目标:在O(n)中找到这些重复数字并仅使用常量存储空间.
例如,设n为7,数组为{1,2,3,1,3,0,6},答案应为1和3.我在这里检查了类似的问题,但答案使用了一些数据结构等HashSet.
任何有效的算法都相同？
我最近在某个地方遇到过一个问题:
假设您有一个1001整数的数组.整数是随机顺序,但您知道每个整数在1到1000之间(包括1和1000).此外,每个数字在数组中只出现一次,但一个数字除外,它出现两次.假设您只能访问数组的每个元素一次.描述一个算法来查找重复的数字.如果您在算法中使用了辅助存储,是否可以找到不需要它的算法？
我感兴趣的是第二部分,即不使用辅助存储.你有什么主意吗？