题目描述
给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。
请找出数组中任意一个重复的数,但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
算法1
(桶的思想) $O(n)$
弄一堆桶标记就ok了桶为2说明重复。
不多bb了。
算法2
(暴力枚举异或和为0) $O(n^2)$
暴力n^2枚举每两个数,异或和为0说明相同。
空间复杂度
无消耗额外空间。
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
for(int i = 0; i < nums.size(); i ++ )
{
for(int j = 0; j < nums.size(); j ++)
{
if(i == j)
continue;
if((nums[i] ^ nums[j]) == 0)
return nums[j];
}
}
}
};