免费金融网站模板,莱州信息网电话,网站制作怎样做背景,建网站哪家最好#x1f3a5; 个人主页#xff1a;Dikz12#x1f525;个人专栏#xff1a;算法(Java)#x1f4d5;格言#xff1a;吾愚多不敏#xff0c;而愿加学欢迎大家#x1f44d;点赞✍评论⭐收藏
目录
归并排序
代码实现
交易逆序对的总数
题目描述
编辑 题解
代码实… 个人主页Dikz12个人专栏算法(Java)格言吾愚多不敏而愿加学欢迎大家点赞✍评论⭐收藏
目录
归并排序
代码实现
交易逆序对的总数
题目描述
编辑 题解
代码实现 计算右侧小于当前元素的个数
题目描述
编辑 题解 代码实现 翻转对
题目描述
编辑 题解
代码实现 归并排序 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 ,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子 序列段间有序。若 将两个有序表合并成一个有序表 称为二路归并。 时间复杂度O(N*logn) ⼤体过程分为两步 分将数组⼀分为⼆为两部分⼀直分解到数组的⻓度为 1 使整个数组的排序过程被分为 「左半部分排序」 「右半部分排序」 治将两个较短的「有序数组合并成⼀个⻓的有序数组」⼀直合并到最初的⻓度。
代码实现
class Solution {int[] tmp;public int[] sortArray(int[] nums) {tmp new int[nums.length];mergeSort(nums,0,nums.length-1);return nums;}public void mergeSort(int[] nums,int left,int right) {if(left right) {return;}//1.根据中间点拆分数据.左、右两部分int mid (left right) / 2;mergeSort(nums,left,mid);mergeSort(nums,mid1,right);//2.合并两个有序数组// int[] tmp new int[right - left 1];int cur1 left,cur2 mid 1,i 0;while(cur1 mid cur2 right) {tmp[i] nums[cur1] nums[cur2] ? nums[cur1] : nums[cur2];}while(cur1 mid) {tmp[i] nums[cur1];}while(cur2 right) {tmp[i] nums[cur2];}// 3.还原到原数组for(int j left; j right; j) {nums[j] tmp[j - left];}}
}
交易逆序对的总数
题目描述 题解 因此我们可以利⽤归并排序的过程先求出左半数组中逆序对的数量再求出右半数组中逆序对的 数量最后求出⼀个选择左边另⼀个选择右边情况下逆序对的数量三者相加即可。 利⽤数组的有序性快速统计 出逆序对的数量⽽不是将所有情况都枚举出来 最核心的问题如何在合并两个有序数组的过程中统计出逆序对的数量 找出该数之前有多少个数比它大找出该数之后有多少个数比它小. 代码实现 int[] tmp;public int reversePairs(int[] nums) {tmp new int[nums.length];return mergerSort(nums,0,nums.length - 1);}public int mergerSort(int[] nums,int left,int right) {//1.递归出口if(left right) {return 0;}// 2.分成左右两部分int ret 0;int mid (left right) 1;ret mergerSort(nums,left,mid);ret mergerSort(nums,mid 1,right);//3.合并// int[] tmp new int[right - left 1];int cur1 left, cur2 mid 1, i 0;//数组下标while(cur1 mid cur2 right) {if(nums[cur1] nums[cur2]) {tmp[i] nums[cur1];}else {//计数ret mid - cur1 1;tmp[i] nums[cur2];}}while(cur1 mid) {tmp[i] nums[cur1];}while(cur2 right) {tmp[i] nums[cur2];}// 还原数组for(int j left; j right; j) {nums[j] tmp[j - left];}return ret;} 计算右侧小于当前元素的个数
题目描述 题解 解法归并排序. 代码实现 int[] ret; // 结果数组int[] index; // 存放原始数据的下标int[] tmpNums; // 辅助数组int[] tmpIndex;public ListInteger countSmaller(int[] nums) {int n nums.length;ret new int[n];index new int[n];tmpIndex new int[n];tmpNums new int[n];// 初始化原始数据的下标for (int i 0; i n; i) {index[i] i;}// 归并排序mergerSort(nums, 0, n - 1);//ListInteger list new ArrayList();for (int x : ret) {list.add(x);}return list;}public void mergerSort(int[] nums, int left, int right) {// 1.递归出口if (left right) {return ;}// 2.拆分成左右两部分int mid (left right) 1;mergerSort(nums, left, mid);mergerSort(nums, mid 1, right);// 合并int cur1 left, cur2 mid 1, i 0;while (cur1 mid cur2 right) {// 降序排 谁大动谁if (nums[cur1] nums[cur2]) {tmpNums[i] nums[cur2];// 绑定移动tmpIndex[i] index[cur2];} else {ret[index[cur1]] right - cur2 1;tmpNums[i] nums[cur1];tmpIndex[i] index[cur1];}}while (cur1 mid) {tmpNums[i] nums[cur1];tmpIndex[i] index[cur1];}while (cur2 right) {tmpNums[i] nums[cur2];tmpIndex[i] index[cur2];}for(int j left; j right; j) {nums[j] tmpNums[j - left];index[j] tmpIndex[j - left];}} 翻转对
题目描述 题解 翻转对和逆序对的定义⼤同⼩异逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要 ⼤于 后⾯某个数的两倍 。因此我们依旧可以⽤归并排序的思想来解决这个问题。 但是归并排序要求的是左边元素大于右边元素而这道题的条件是左边元素大于右边元素的两倍所以 我们需要在归并之前完成翻转对的统计。 代码实现 int[] tmp;public int reversePairs(int[] nums) {int n nums.length;tmp new int[n];return mergerSort(nums,0,n - 1);}public int mergerSort(int[] nums,int left,int right) {//1.递归结束条件if(left right) {return 0;}//2.拆分数组分为左右两部分int ret 0;int mid (left right) 1;ret mergerSort(nums,left,mid);ret mergerSort(nums,mid 1,right);//3.计算翻转对(降序)int cur1 left,cur2 mid 1,i 0;while(cur1 mid) {// while(cur2 right nums[cur2] nums[cur1] / 2.0 ) {// ret right - cur2 1;// cur1;// }// if(cur2 right) {// break;// }// cur2;while(cur2 right nums[cur2] nums[cur1] / 2.0) {cur2;}if(cur2 right) {break;}ret right - cur2 1;cur1;}//4.合并两个有序数组cur1 left;cur2 mid 1;while(cur1 mid cur2 right) {if(nums[cur1] nums[cur2]) {tmp[i] nums[cur2];}else{tmp[i] nums[cur1];}}while(cur1 mid) {tmp[i] nums[cur1];}while(cur2 right) {tmp[i] nums[cur2];}for(int j left; j right; j) {nums[j] tmp[j - left];}return ret;}
