算法
(数组遍历) $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;
}
呵呵
为什么没人用桶排做呢
实测速度还慢了一点
我用了,两题我都这么做的
桶排用了额外的空间,有时候算法要求使用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看一下
请问用map效率是不是低很多.
不会低很多。不过面试题也会看重空间。
时间 多了一个log,空间多一个二叉树
y总你好,这里有一个问题第二个for循环是不是可以将它去掉for (int i = 0; i < n; i ++ ) {},因为while循环过后已经将除了第一个元素的所有的元素都放在了正确的位置上了,再从第二个位置上开始已经没什么意义了,我下面的写法也可以通过,难道是我想错了吗?
int n =nums.length;
if(n == 0) return -1;
for(int x:nums)
{
if(x < 0 || x >= n)
return -1;
}
y总我想了一下,明白了,当第一个位置已经是0而重复元素出现在后面时,这种情况就不满足了。但是测试用例没有这种情况,所以也能ac。
数据已加强,增加了这种情况。