。

请编写代码找出那个缺失的整数。

你有办法在O(n)时间内完成吗#xff1f;

2、题目分析

#xff08;1#xff09;numsS…本博客的OJ标题均已插入超链接点击可直接跳转~

1、题目描述

数组nums包含从0到n的所有整数但其中缺了一个。

请编写代码找出那个缺失的整数。

你有办法在O(n)时间内完成吗

2、题目分析

暴力旋转——将最后一个数用tmp存起来剩下的数依次往后挪再把tmp放到数组首位循环往复直至满足题意

从示例1不难看出真实旋转次数是k%numsSize也就是k%N从周期的角度就可以理解这一点每转一次就要把整个数组动一遍那转k次就要动k*N遍时间复杂度就出来了显然不符合题目要求

3思路二

分析本算法的时间复杂度可以看出遍历了3次数组复杂度为ON满足题目要求

具体代码实现如下

tmpnums[left];nums[left]nums[right];nums[right]tmp;left;right--;}}

void

{kk%numsSize;//算出真正的轮转次数reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);

}二、

retN(N1)/2//此处计算参考等差数列求和公式for(int

i0;inumsSize;i){retret-nums[i];}return

ret;

i0;inumsSize;i){xx^nums[i];}for(int