17.04.消失的数字
- 这里题目要求在时间复杂度上
O(n)我们介绍三种方法，看看哪种方法适合这道题~~
方法一：
- 先冒泡排序
- 遍历，当前值+1，不等于下一个数
这个时间复杂度是O(N^2)
方法二：
- 将数组的每个元素异或0
- 遍历，再将异或出来的结果每个再异或
这个时间复杂度是
O(N)
方法三：
- 0到n等差数列公式计算和
((首项 + 尾项) * 项数)/2 - 依次减掉数据中的值，剩下的就是消失的数字
这个时间复杂度是
O(N)
- 可见只有方法二和方法三符合题目要求，下面我们就写一下这个代码
方法二的代码
int missingNumber(int* nums, int numsSize){ int N = numsSize; int sum = ((0+N)*(N+1))/2; for(int i= 0;i<numsSize;i++){ sum-=nums[i]; } return sum; }
方法三的代码
int missingNumber(int* nums, int numsSize){ int x = 0; for(int i = 0;i<numsSize;i++){ x^=nums[i]; } for(int i = 0;i<=numsSize;i++){ x^=i; } return x; }
189.旋转数组
- 我们这个题肯有些同学在C语言的时候做过
思路一
我们先来看思路一：
- 思路一的时间复杂度是多少？
- 可能有的同学算出来的是
O(N*K)，不完全正确~~
- 最好的情况：k % N = 0，k = 7，旋转0次！！！是
O(1)。k是N的倍数时，不需要旋转~~ - 最坏的情况：k % N = N - 1时，比如13次旋转的最多，20次最多…
- 所以这个题的真正复杂度是
O（N*(N-1)）—>O(N^2)
那么我们要求时间复杂度是
O(N)，那么我们怎么优化呢？
思路二
我们这里就要看思路二：
- 这里很明显是
O(N)
代码如下：
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; } reverse(nums,0,numsSize-1); reverse(nums,0,k-1); reverse(nums,k,numsSize-1); }
- 注意这里k一定要%numsSize，否则会报错~~
思路三
空间换时间
- 这里的时间复杂是
O(N)，空间复杂度是O(N)
代码如下：
void rotate(int* nums, int numsSize, int k) { k %= numsSize; int tmp[numsSize]; int j = k; //拷贝前n-k个 for (int i = 0; i < numsSize - k; i++) { tmp[j++] = nums[i]; } //拷贝后k个 j = 0; for (int i = numsSize - k; i < numsSize; i++) { tmp[j++] = nums[i]; } //拷贝回原数组 for (int i = 0; i < numsSize; i++) { nums[i] = tmp[i]; } }
