对于网站建设的体会,保定网站建设培训班,网上购物的商城都有哪些,申请个人网站多少钱废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【数组合并】#xff0c;使用【数组】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为…废话不多说喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【数组合并】使用【数组】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。 名曲目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
合并两个有序数组【EAZY】
其实这道题的思路和合并两个有序链表大同小异
题干
直接粘题干和用例
解题思路
给出解题思路最好有图
step 1使用三个指针i指向数组A的最大元素j指向数组B的最大元素index指向数组A空间的结尾处。step 2从两个数组最大的元素开始遍历直到某一个结束每次取出较大的一个值放入数组A空间的最后然后指针一次往前。step 3如果数组B先遍历结束数组A前半部分已经存在了不用管但是如果数组A先遍历结束则需要把数组B剩余的前半部分依次逆序加入数组A前半部分类似归并排序最后的步骤。 代码实现
给出代码实现基本档案 基本数据结构数组 辅助数据结构无 算法迭代 技巧双指针逆序双指针 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;
public class Solution {public void merge(int A[], int m, int B[], int n) {// 1 入参校验数组长度需要满足条件if (A null || A.length m n) {return;}// 2 因为A数组后几位是空着的为了不让前面元素的移动引起的挪动导致整个A发生元素移动问题可以转换为找最大值先把最大值放到最后的空位置int maxIndex m n - 1;int i m - 1;int j n - 1;// 双指针从大到小移动,比较A和B的元素将较大的放到A中后边的位置while (i 0 j 0) {A[maxIndex--] A[i] B[j] ? A[i--] : B[j--];}// 如果B还有剩余合并到A中如果是A有剩余无需合并到A中while (j 0) {A[maxIndex--] B[j--];}}
}复杂度分析
时间复杂度O(mn)。 指针移动单调递增最多移动 mn 次因此时间复杂度为 O(mn)。空间复杂度O(mn)。 需要建立长度为 mn 的中间数组
