建设网站设计公司,制作网站加背景怎么做流程,中煤第五建设有限公司网站,wordpress 上传腾讯云直接排序
直接使用Java已有的方法进行排序#xff0c;这一招…大意了#xff01;
这题简单#xff0c;就是个基本的排序#xff0c;后面难题#xff0c;可能这只是一小步#xff0c;内个时候直接用排序算法比较合适#xff0c;这个不合适。。
class Solution {public…
直接排序
直接使用Java已有的方法进行排序这一招…大意了
这题简单就是个基本的排序后面难题可能这只是一小步内个时候直接用排序算法比较合适这个不合适。。
class Solution {public void merge(int[] A, int m, int[] B, int n) {for(int i 0; i n; i){A[mi] B[i];}Arrays.sort(A);}
}我们看看方法 这是一个更优的快速排序算法对于某些数据传统的快速排序可能会退化为二次方的事件复杂度而此算法会更快一些是O(n log(n))。
这种方式顶多算应用黑箱子没啥可以说的…
双指针 临时数组
我们可以对每个数组都添加一个索引指针依次对比两个数组的值让最小的进入临时数组比较之后把剩余的数直接放入临时数组最后临时数组再赋值给A。
leetcode的动图很好直接放出来链接。
双指针
class Solution {public void merge(int[] A, int m, int[] B, int n) {int[] temp new int[mn];int i 0; // array A pointerint j 0; // array B pointerint k 0; // array temp pointerwhile(i m j n){if(A[i] B[j]){temp[k] A[i];} else if(A[i] B[j]){temp[k] B[j];} }// 剩余部分while(i m){temp[k] A[i];}while(j n){temp[k] B[j];}k 0;i 0;while(k m n){A[i] temp[k];}}
}这种方法实现起来很简单其实就是依次比较但是开辟新的数组再放回去就很麻烦。
同样的思路不同的实现方式
对于同样的逻辑代码写起来其实也不一定一样的我们看一看
逆向双指针
所以我们尝试一下在数组A直接动手脚利用数组A中后半部分的剩余空间看看可不可行
关键点A中的元素会不会被覆盖 我们可以从两数组的后面开始比较谁大将大的放进A的最后面。 这里我们列举极端例子
B中的元素全部比A中最大的还大
那么中的元素全部放入A的剩余空间中去显然没有问题 2. B的元素比A的元素都小 当然也能放进去。
最后我们看看中间状态也就是正常状态 很容易分析得出不管怎么样A中的剩余空间一定够用
因此写代码实现
class Solution {// 逆向双指针public void merge(int[] A, int m, int[] B, int n) {int ap m - 1;int bp n - 1;int final_pointer m n - 1;while(ap 0 bp 0){if(A[ap] B[bp]){A[final_pointer--] A[ap--];} else{A[final_pointer--] B[bp--];}}// 若A剩余就不用管了若B剩余都扔进去while(bp 0){A[final_pointer--] B[bp--];}}
}或者可以
class Solution {// 逆向双指针public void merge(int[] A, int m, int[] B, int n) {int ap m - 1;int bp n - 1;int final_pointer m n - 1;while(bp 0){// 置换A的元素if(ap 0 A[ap] B[bp]){ // 注意顺序不要写反A[final_pointer--] A[ap--];} else {// 置换B的元素A[final_pointer--] B[bp--];}}}
}后者写法简洁一些前者写法更加明了是继承解法二的思想。
我们用严格的方式再说明一下A不会被覆盖的问题。
我们只需要满足
A中可用的位置 A已经置换的数量 B已经置换的数量
因此我们分别表示一下 我们要求的是白格子的数量是
n - (pb 1) n - pb - 1pb是索引从0开始因此橙色一共pb 1个总数是n减一下就行了
A同理
m - pa - 1 当前数组A可插入数量应该是m n - pa - 1。
我们求的这三个数分别是在同一时刻
f1:A扔到A后面去的f2:B扔到A后面去的f3:A后面总共可以插入的元素不被覆盖的情况下
我们只需要验证f3 f1 f2恒成立即可 pa -1显然恒成立。
