LeetCode | 17.04.消失的数字和189.旋转数组

本文主要是介绍LeetCode | 17.04.消失的数字和189.旋转数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode | 17.04.消失的数字和189.旋转数组

文章目录

LeetCode | 17.04.消失的数字和189.旋转数组
17.04.消失的数字
- 方法一：
- 方法二：
- 方法三：
- - 方法二的代码
  - 方法三的代码
189.旋转数组
- 思路一
- 思路二
- 思路三

17.04.消失的数字

OJ链接

这里题目要求在时间复杂度上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.旋转数组

OJ链接

在这里插入图片描述

我们这个题肯有些同学在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];}
}