算法
(数组遍历) $O(n)$
首先遍历一遍数组，如果存在某个数不在0到n-1的范围内，则返回-1。
下面的算法的主要思想是把每个数放到对应的位置上，即让 nums[i] = i。
从前往后遍历数组中的所有数，假设当前遍历到的数是 $nums[i] = x$，那么：
- 如果
x != i && nums[x] == x，则说明 $x$ 出现了多次，直接返回 $x$ 即可； - 如果
nums[x] != x，那我们就把 $x$ 交换到正确的位置上，即swap(nums[x], nums[i])，交换完之后如果nums[i] != i，则重复进行该操作。由于每次交换都会将一个数放在正确的位置上，所以swap操作最多会进行 $n$ 次，不会发生死循环。
循环结束后，如果没有找到任何重复的数，则返回-1。
时间复杂度分析
每次swap操作都会将一个数放在正确的位置上，最后一次swap会将两个数同时放到正确位置上，一共只有 $n$ 个数和 $n$ 个位置，所以swap最多会进行 $n - 1$ 次。所以总时间复杂度是 $O(n)$。
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = nums.size();
for (auto x : nums)
if (x < 0 || x >= n)
return -1;
for (int i = 0; i < n; i ++ ) {
while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
if (nums[i] != i) return nums[i];
}
return -1;
}
};
class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
int n=nums.size();
for(auto x:nums)//对nums中逐个元素的复制引用
{
if(x<0||x>=n)
return -1;
}
for(int i=0;i<n;i)
{
for(int j=i+1;j<n;j)
{
if(nums[i]==nums[j])
return nums[i];
}
}
return -1;
}
};
这样写为啥错了？
不可以直接排序，然后再找重复的吗
可以，但这样就慢了
经典题目
先遍历是保证剩下的所有数都满足0~n-1，之后等于是在做排序，搞了省空间的排序？
我是只会循环的小菜
我不李姐这错了啥？
语言:C
#include[HTML_REMOVED]
using namespace std;
int main(){
int n,sum=0,z,h,b[10001],c;
cin>>n;
int a[n];
for(int i=0;i[HTML_REMOVED]>a[i];
b[h]=a[i];
h;
z=a[i];
for(int x=0;x<=sum+1;x){
if(b[x]==z){
c=b[x];
sum;
}
}
}
if(sum==0){
cout<<”-1”;
}else{
cout<<c;
}
return 0;
}
要在他给的class里面写
呵呵
为什么没人用桶排做呢
实测速度还慢了一点
我用了，两题我都这么做的
桶排用了额外的空间，有时候算法要求使用O1的空间来做，这个思路挺好的。当然桶排也是一个解法
class Solution是什么
？
类似于leetcode的核心代码模式
哦，谢谢
从第一个nums[0]开始感觉就对不上了，nums[0]!=0,那不是直接返回nums[0]的值了嘛
交换之后，如果还相等，说明他是重复的
class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
int i,n=nums.size();
for(auto x:nums)
if(x<0||x>=n)
return -1;
for(i=0;i<n;i)
for(int j=i+1;j<n;j)
if(nums[i]==nums[j])
return nums[i];
return -1;
}
};
这个方法绝了，强
奇奇怪怪的想法，诀绝子
y总，这题如果使用map，空间复杂度和时间复杂度各是多少呢，都是logN吗
请问要是只输出第一个重复数字该怎么改呢？[6,3,2,0,2,5,0]比如这个输出就是0 但是实际应该是2
我是考虑先使用sort对nums进行排序，只要找到两个相邻的数值相同就返回当前数值
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == nums[i + 1])
return nums[i];
}
你这个输出不是0？，难道不应该是2？
不用sort,直接map过,或者n小的话桶排，从头到尾遍历数字对应的第一个达到数字的统计>1,就return
循环从1开始遍历也过了
互反性，可以看成swap(nums[nums[i]],nums[i]), 如果有，也会定位到nums[0]。
代码简洁明了！
class Solution {
public int duplicateInArray(int[] nums) {
for(int i:nums){
if(i>=nums.length||i<0) return -1;
}
for(int i=0;i<nums.length;i++){
while(nums[nums[i]]!=nums[i]){
int temp=nums[i];
nums[i]=nums[nums[i]];
nums[nums[i]]=temp;
}
if(nums[i]!=i) return nums[i];
}
return -1;
}
}
麻烦大家帮忙看看我这啥问题，就是跑不出来
int temp=nums[i];
nums[i]=nums[nums[i]];
nums[nums[i]]=temp;
这部分交换有问题，执行完nums[i]=nums[nums[i]];后，nums[i]已经变化，nums[nums[i]]也跟着变了，最后nums[nums[i]]的索引值就已经改了。
建议debug看一下