企业官网建设流程全解析

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

力扣88. 合并两个有序数组

链接：https://leetcode.cn/problems/merge-sorted-array/description/

注意点

倒序双指针做法。

这道题的题目关键在于答案怎么放入。

1.设计三个指针，分别直接指向nums1, nums2, nums的末尾。

2.当num2的指针没有指向0的时候，即nums2中的元素还没合并完的时候，分为两种情况，一种是nums1[len1]的值大于等于nums2[len2]，这个时候就需要将nums1[len]赋值为nums1[len1]，把nums1的元素插入到对应的位置，同时len和len1同时往前移动一格；反之同理。

3.这道题如果从前面插入元素的话，那么如果遇到先将nums2的元素插入到nums1中，就会出现覆盖的情况，因此不建议这么做。那为啥可以从后面插入元素呢，因为这道题目输入的nums1已经为m+n长度的。

代码

class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int len1 = m - 1; int len2 = n - 1; int len = m + n - 1; while (len2 >= 0) { if (len1 >= 0 && nums1[len1] >= nums2[len2]) { nums1[len --] = nums1[len1 --]; } else { nums1[len --] = nums2[len2 --]; } } } }

时空复杂度分析

单层循环，会碰到len2和len1长度的数组都遍历的情况。所以时间复杂度为O(m+n)

空间复杂度为O(1)

洛谷T227292 【排序】合并两个有序数组

链接：https://www.luogu.com.cn/problem/T227292#ide

注意点

同上

代码

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int mx = 1000001; int[] nums1 = new int[mx]; for (int i = 0; i < n; i ++) { nums1[i] = sc.nextInt(); } int m = sc.nextInt(); int[] nums2 = new int[mx]; for (int i = 0; i < m; i ++) { nums2[i] = sc.nextInt(); } int len1 = n - 1; int len2 = m - 1; int len = n + m - 1; while (len2 >= 0) { if (len1 >= 0 && nums1[len1] >= nums2[len2]) nums1[len --] = nums1[len1 --]; else nums1[len --] = nums2[len2 --]; } for (int i = 0; i <= n + m - 1; i ++) { System.out.print(nums1[i] + " "); } } }

时空复杂度分析

同上

力扣977. 有序数组的平方

链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

注意点

相向指针做法。

这道题的题目关键在于将计算后的平方结果有序放入。

1.设计两个指针，一头一尾。

2.核心逻辑就是，计算完平方之后，遍历原始位置，把大的数从后往前放入数组中即可。

代码

class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] ans = new int[n]; int i = 0; int j = n - 1; for (int p = n - 1; p >= 0; p --) { int x = nums[i] * nums[i]; int y = nums[j] * nums[j]; if (x > y) { ans[p] = x; i ++; } else { ans[p] = y; j --; } } return ans; } }

时空复杂度分析

单层循环，需要遍历n次，因此时间复杂度为O(n)

空间复杂度为O(1)

参考

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html