成都学生做网站,400免费服务电话申请,关键词网站排名软件,网站建设推广找stso88效果好文章目录 一、排序思想的题目二、使用步骤1. 一、排序思想的题目
跟着b站一周刷爆leetcode这个视频开始刷一下leetcode的题目 进行一下记录啥的
二、使用步骤
1.
315. 计算右侧小于当前元素的个数 代码如下#xff1a; 写了一下暴力解法#xff0c;没有通过 使用归并排序… 文章目录 一、排序思想的题目二、使用步骤1. 一、排序思想的题目
跟着b站一周刷爆leetcode这个视频开始刷一下leetcode的题目 进行一下记录啥的
二、使用步骤
1.
315. 计算右侧小于当前元素的个数 代码如下 写了一下暴力解法没有通过 使用归并排序进行优化实则就是把大问题分成各个小问题简化为如果我左端大于你第二个的左端了那你后面的也不用看了直接r-l1就是个数
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;class solution {// ListInteger res new ArrayList();// for(int i 0; i nums.length; i){// int t 0;// for(int j i 1;j nums.length; j){// if(nums[i] nums[j]){// t;// }// }// res.add(t);// }// return res;public void process(int[] nums, int l, int r, ListInteger list, int[] index){int mid l ((r - l) 1);if( l r){return ;}// 正常的归并process(nums,l,mid, list, index);process(nums,mid 1,r, list, index);merge(nums,l,mid,r,list, index);}// 归并public void merge(int[] nums,int l,int m,int r,ListInteger list,int[] index){// index是用来存原来下标的移动的因为要返回原来对应的一个列表只能这样记录了int[] temp new int[r - l 1];int[] tempIndex new int[r - l 1];int p1 l;int p2 m 1;int i 0;// 左右指针开始移动while(p1 m p2 r){if(nums[p1] nums[p2]){temp[i] nums[p2]; //塞进去tempIndex[i] index[p2]; // 塞下标i;p2;}else{//关键点当左指针大于右指针的时候右边直接归纳个数即可list.set(index[p1],list.get(index[p1])r-p21); // 右比左小则加长度temp[i] nums[p1];tempIndex[i] index[p1];i;p1;}}while(p1 m){temp[i] nums[p1];tempIndex[i] index[p1];i;p1;}while(p2 r){temp[i] nums[p2]; //塞进去tempIndex[i] index[p2]; // 塞下标i;p2;}for(int k 0; k temp.length;k ){nums[k l] temp[k];index[k l] tempIndex[k];}}public ListInteger countSmaller(int[] nums) {// 存放结果ListInteger list new ArrayList(Collections.nCopies(nums.length, 0));int[] index new int[nums.length];for(int i 0;i nums.length;i){index[i] i;}process(nums,0,nums.length-1,list,index);return list;}}// 测试用例
public class test{public static void main(String[] args) {int [] test {-1,-1};solution s new solution();s.countSmaller(test);}
}
