如何建立自己的超市网站,抚州教育网站建设,新人怎么做电商,个人网站设计论文模板本博客的OJ标题均已插入超链接#xff0c;点击可直接跳转~
一、消失的数字
1、题目描述
数组nums包含从0到n的所有整数#xff0c;但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗#xff1f;
2、题目分析
#xff08;1#xff09;numsS…本博客的OJ标题均已插入超链接点击可直接跳转~
一、消失的数字
1、题目描述
数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗
2、题目分析
1numsSize表示的是数组中元素的个数
2思路一
暴力旋转——将最后一个数用tmp存起来剩下的数依次往后挪再把tmp放到数组首位循环往复直至满足题意 这里需要理清这个算法的时间复杂度解析如图设numsSizeN 从示例1不难看出真实旋转次数是k%numsSize也就是k%N从周期的角度就可以理解这一点每转一次就要把整个数组动一遍那转k次就要动k*N遍时间复杂度就出来了显然不符合题目要求
3思路二
三步逆置法
第一步前N-k个逆置4 3 2 1 5 6 7第二步后k个逆置4 3 2 1 7 6 5第三步整体逆置5 6 7 1 2 3 4 分析本算法的时间复杂度可以看出遍历了3次数组复杂度为ON满足题目要求 具体代码实现如下
//三步逆置法
void reverse(int*nums,int left,int right)
{while(left right){int tmpnums[left];nums[left]nums[right];nums[right]tmp;left;right--;}}
void rotate(int* nums, int numsSize, int k)
{kk%numsSize;//算出真正的轮转次数reverse(nums,0,numsSize-k-1);reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-1);
}二、 旋转数组/轮转数组
1、题目描述
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
2、题目分析 思路1由于排序的时间复杂度较高先舍弃掉
1思路二
先把0-N所有数加起来然后依次减去原数组中的值
int missingNumber(int* nums, int numsSize)
{int NnumsSize;int retN(N1)/2//此处计算参考等差数列求和公式for(int i0;inumsSize;i){retret-nums[i];}return ret;
}2思路三
用异或解决此处异或满足“交换律”读者可自行验证 举例来说1 ^ 2 ^ 12,1 ^ 1 ^ 22 具体代码实现如下
int missingNumber(int* nums, int numsSize)
{int x0;for(int i0;inumsSize;i){xx^nums[i];}for(int i0;inumsSize;i){xx^i;}return x;
}
