企业网站建设解决方案,window优化大师,c语言网站开发,自建国外购物网站目录
一、消失的数字
思路一#xff08;暴力求解#xff09;代码实现#xff1a;
思路二#xff08;数列的思想#xff09;代码实现#xff1a;
思路三#xff08;异或的运用#xff09;代码实现#xff1a; 二、轮转数组
思路一#xff08;暴力求解#xff09…目录
一、消失的数字
思路一暴力求解代码实现
思路二数列的思想代码实现
思路三异或的运用代码实现 二、轮转数组
思路一暴力求解代码实现
思路二使用额外的空间以空间换时间代码实现
思路三三步逆置 一、消失的数字 思路如下图 思路一暴力求解代码实现
排序好后一一查找。
此处不建议使用该方法因为时间复杂度过大。 int missingNumber(int* nums, int numsSize)
{int i 0;int j 0;int flag -1;//利用冒泡排序思想进行排序for (i 0; i numsSize - 1; i){for (j 0; j numsSize - 1 - i; j){if (nums[j] nums[j 1]){int tmp nums[j];nums[j] nums[j 1];nums[j 1] tmp;}}}//一个个查找for (i 0; i numsSize; i){if (i ! nums[i]){flag i;break;}}return i;
}思路二数列的思想代码实现
此处代码就开始简化了时间复杂度为O(N)先用上等差数列的公式求前num个数字之和再一一减去nums数组中的元素最后得到的就是消失的数字
int missingNumber(int* nums, int numsSize)
{int i0;int sum0;//前numsSize个数字相加等差数列求和sum (numsSize1)*numsSize/2;//减去nums数组中的所有值的和for(i0;inumsSize;i){sum-nums[i];}return sum;
}
思路三异或的运用代码实现 利用了异或操作符 首先讲解一下这个操作符^ 这个操作符是对二进制来用的相同为零相异为一 这个操作符有几个特点 1.n^0 n 2.n^n 0 3.满足交换律,如(a^b) ^ c a^b^c 如果想知道更多操作符的使用请移步到操作符笔记-CSDN博客
思路:用0先跟0~numsSize中数据异或再跟nums数组中所有元素异或最后的值就是所要找的值
效果如下
0^1^2^...中间有消失的数...^n ^1^2^...中间消失的数不在这里...^n 0^中间有消失的数
中间有消失的数
int missingNumber(int* nums, int numsSize)
{int x 0;int i 0;//先跟0-numsSize中数据异或for (i 1; i numsSize; i){x x ^ i;}//跟nums数组中数据异或for (i 0; i numsSize; i){x x ^ nums[i];}return x;} 二、轮转数组 思路如下图所示 思路一暴力求解代码实现 void rotate(int* nums, int numsSize, int k) {//如果knumsSize,则kk%numsSize减少循环次数if (k numsSize){k % numsSize;}//轮转的次数for (int j 1; j k; s){//记录数组最后一个元素的值int tmp nums[numsSize-1];//每一次的轮转数组的变化for (int i numsSize - 1; i 0; i--){nums[i] nums[i - 1]; }//把记录下来的值赋给数组首元素nums[0] tmp;}
} 思路二使用额外的空间以空间换时间代码实现
牺牲存储空间为代价直接在栈上开辟一块新的存储空间 void rotate(int* nums, int sz, int k)
{//开辟与nums数组一样大小的空间int* tmp (int*)malloc(sizeof(int) * sz);int i 0;//如果ksize,则kk%size减少循环次数if (k sz){k % sz;}//先把后sz-k-1个元素拷贝到tmp中去for (i 0; i k; i){tmp[i] nums[sz - k i];}//再把前k-1个元素拷贝到tmp中去for (i 0; i sz-k; i){tmp[ki] nums[i];}//最后把tmp的内容拷贝到nums中去for (i 0; i sz; i){nums[i] tmp[i];}
}
思路三三步逆置 如果knumsSize时取余数
因为逆置8次和逆置1次效果是相同的
void reverse(int* nums, int left, int right) {while (left right) {int tmp nums[left];nums[left] nums[right];nums[right] tmp;left;right--;}
}void rotate(int* nums, int numsSize, int k) {if(knumsSize){k % numsSize; // 如果k大于等于数组长度先对k取余}reverse(nums, 0, numsSize - k - 1);//注意控制下标reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}
