一、消失的数字
思路如下图：
思路一（暴力求解）代码实现：
排序好后一一查找。
此处不建议使用该方法，因为时间复杂度过大。
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 i=0; int sum=0; //前numsSize个数字相加，等差数列求和 sum = (numsSize+1)*numsSize/2; //减去nums数组中的所有值的和 for(i=0;i<numsSize;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) { //如果k>=numsSize,则k=k%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; //如果k>=size,则k=k%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[k+i] = nums[i]; } //最后，把tmp的内容拷贝到nums中去 for (i = 0; i < sz; i++) { nums[i] = tmp[i]; } }
思路三（三步逆置）
如果k>=numsSize时，取余数
因为，逆置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(k>=numsSize) { k %= numsSize; // 如果k大于等于数组长度，先对k取余 } reverse(nums, 0, numsSize - k - 1); //注意控制下标 reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); }
