一周刷爆leetcode！（b站视频）

---

一、排序思想的题目

跟着b站一周刷爆leetcode这个视频开始刷一下leetcode的题目
进行一下记录啥的

二、使用步骤

1.

315. 计算右侧小于当前元素的个数
代码如下：
写了一下暴力解法，没有通过
使用归并排序进行优化，实则就是把大问题分成各个小问题，（简化为，如果我左端大于你第二个的左端了，那你后面的也不用看了，直接r-l+1就是个数

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;class solution {// List<Integer> 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, List<Integer> 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,List<Integer> 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-p2+1); // 右比左小，则加长度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 List<Integer> countSmaller(int[] nums) {// 存放结果List<Integer> 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);}
}