LeetcodeHot100打卡（14、合并空间，15、轮转数组，16、除了自身以外数组乘积，17.缺失的第一个整数）-编程实验室

学习时整理，如有错误，欢迎指正

14、合并空间

56. 合并区间 - 力扣（LeetCode）

classSolution{publicint[][]merge(int[][]intervals){//先把intervals按左端点从小到大进行排列Arrays.sort(intervals,(p,q)->p[0]-q[0]);//答案链表，最后要改为数组List<int[]>ans=newArrayList<>();for(int[]p:intervals){//动态维护m值，始终为ans的最后一项intm=ans.size();if(m>0&&p[0]<=ans.get(m-1)[1])//左端点小于前一区间的右端点，需要合并{ans.get(m-1)[1]=Math.max(ans.get(m-1)[1],p[1]);//看右端点取哪个//前区间的右端点大，则后区间整个被包住//后区间的右端点大，则区间有交集}else{//不相交，无法合并ans.add(p);}}returnans.toArray(newint[ans.size()][]);}}

题目要求，把连续的区间合并为一个

可以先把目光放在两个小区间A,B上（A左端点小于B）

如果A的右端点小于B的左端点，两区间无交集，无法合并
如果A的右端点小于B的左端点，两区间有交集，需要合并
- 此时如果A的右端点大与B的右端点，则后区间整个被包住
- 此时如果B区间的右端点大，则区间有交集

放在整体中，需要对每两个相邻小区间进行这样的操作，需要对整个序列按左端点从小到大进行排列

另外，在具体实现中，需要动态维护参数m值，始终为ans的最后一项

开始时ans为链表，方便添加元素

最后变为符合形式的二维数组

时间复杂度为： O(nlogn)

空间复杂度： O(n)

15、轮转数组

189. 轮转数组 - 力扣（LeetCode）

classSolution{publicvoidrotate(int[]nums,intk){intn=nums.length;k%=n;reverse(nums,0,n-1);reverse(nums,0,k-1);reverse(nums,k,n-1);}publicvoidreverse(int[]nums,inti,intj){while(i<j){inttemp=nums[i];//i与j在读取后再数值操作nums[i++]=nums[j];nums[j--]=temp;}}}

题目要求我们将数组中的元素向右轮转k个位置。

观察可发现：

右移后，原数组后k个元素会移动到数组前面；
前n-k个元素则整体后移。

例如：

1 2 3 4 5 6 7

当k = 3时，结果为：

5 6 7 1 2 3 4

因此，可以将数组按照n-k的位置划分为两部分：

[1 2 3 4] [5 6 7]

目标就是让后半部分移动到前面，同时保证两部分内部原有顺序不变。

为实现这一点，可以采用“三次反转”：

先整体反转数组

7 6 5 4 3 2 1

再反转前k个元素

5 6 7 4 3 2 1

最后反转后n-k个元素

5 6 7 1 2 3 4

这样即可完成数组右旋，并且保证各部分原有相对顺序不变。

时间复杂度：数组只被遍历了常数次，因此时间复杂度为O(n)。

空间复杂度：只使用了若干临时变量，没有额外开辟数组空间，因此空间复杂度为O(1)。

16、除了自身以外数组乘积

238. 除了自身以外数组的乘积 - 力扣（LeetCode）

classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;intpre[]=newint[n];pre[0]=1;for(inti=1;i<n;i++){pre[i]=pre[i-1]*nums[i-1];}int[]suf=newint[n];suf[n-1]=1;for(inti=n-2;i>=0;i--){suf[i]=suf[i+1]*nums[i+1];}int[]ans=newint[n];for(inti=0;i<n;i++){ans[i]=pre[i]*suf[i];}returnans;}}

某个位置除自身以外的乘积，其实就是：

左边所有元素的乘积
乘上右边所有元素的乘积

这与前缀和思想类似，因此这里可以使用“前缀积 + 后缀积”来解决。

例如：

对于位置i：

pre[i]表示i左侧所有元素乘积
suf[i]表示i右侧所有元素乘积

则当前位置答案为：

pre[i] * suf[i]

因此：

先从左到右计算前缀积
再从右到左计算后缀积
最后将两者相乘即可得到答案

时间复杂度：数组被遍历了若干次，但每次都是线性遍历,O(n)

空间复杂度：使用了pre、suf与ans三个额外数组，因此空间复杂度为：O(n)

另外，本题还可以进行空间优化。

观察发现：

pre数组是从左向右逐步计算的；
并且每个位置的前缀积只会使用一次；

因此无需额外维护整个pre数组，只需要使用一个变量滚动维护当前前缀积即可。

同时，由于最终答案数组与后缀积数组的更新顺序一致，因此可以直接复用suf数组作为答案数组。

优化思路：

先计算每个位置的后缀积；
再使用变量pre动态维护当前位置左侧乘积；
直接将前缀积乘到suf[i]中。

这样便省去了pre与ans两个额外数组。

优化后：

时间复杂度仍为：O(n)
空间复杂度降为：O(1) 这里的O(1)表示除返回答案数组外，仅使用了常数级额外空间。

classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;int[]suf=newint[n];suf[n-1]=1;for(inti=n-2;i>=0;i--){suf[i]=suf[i+1]*nums[i+1];}intpre=1;for(inti=0;i<n;i++){// 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中suf[i]*=pre;pre*=nums[i];}returnsuf;}}

17.缺失的第一个整数

41. 缺失的第一个正数 - 力扣（LeetCode）

原地哈希

不额外开 HashMap / HashSet，
而是直接利用数组下标来充当“哈希表”。

classSolution{publicintfirstMissingPositive(int[]nums){intn=nums.length;for(inti=0;i<n;i++){//nums[i]所处的位置应该在下标为nums[i]-1的地方//如果说目标位置和自己不重复，他就应该在那个位置，进行交换while(1<=nums[i]&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){inttemp=nums[i];intj=nums[i]-1;nums[i]=nums[j];nums[j]=temp;}}//第一个与下标不符合的就是答案for(inti=0;i<n;i++){if(nums[i]!=i+1){returni+1;}}returnn+1;}}