归并排序,可以理解成后序遍历,把根的左子树和右子树分别排序好了之后,在合并为排序好的根
快速排序,可以理解成前序遍历,把在根层选定一个key值划分好两个排序好的区间,分别在给左子树和右子树,女少啊!!!~~~
易错点:int[] tem = new int[right-left+1] 而不是 new int[nums.length];
优化点:tem数组只是一个中间商,不用每次递归都new一个,给他提出来作为全局变量,首次进mergeSort的时候new一个就可以了,会节约不少的资源开销
class Solution {
public int[] sortArray(int[] nums) {
//归并排序
//传入的参数:数组,左边界,右边界
int left = 0 , right = nums.length-1;
mergeSort(nums,left,right);//对整个区间进行排序
return nums;
}
public void mergeSort(int[] nums , int left , int right){
//1:定义出口
if(left >= right) return;
//2:把数组分成两个区间 [left,mid] [mid+1,right]
int mid = (left + right)/2;
//3:把左边区间排个序,再把右边区间排个序
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//4:合并排序好的两个区间
// (1)使用一个tem数组来作为中间人存储排序好的结果
// int[] tem = new int[nums.length];//new一个数组长度是当前划分的区间长度,这一点点代码不优化就跑不过去
int[] tem = new int[right-left+1];
// (2)定义双指针
int cur1 = left , cur2 = mid + 1 , i = 0;
// (3)分别对两个区间排序,放到tem中
while(cur1 <= mid && cur2 <= right){
tem[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
// (4)处理没有遍历完的数组
while(cur1 <= mid) tem[i++] = nums[cur1++];
while(cur2 <= right) tem[i++] = nums[cur2++];
// 5:将tem中的值copy给nums
for(int j = left ; j <= right ; j++){
nums[j] = tem[j-left];
}
}
}
class Solution {
int[] tem;
public int[] sortArray(int[] nums) {
//归并排序
//传入的参数:数组,左边界,右边界
int left = 0 , right = nums.length-1;
tem = new int[nums.length];
mergeSort(nums,left,right);
return nums;
}
public void mergeSort(int[] nums , int left , int right){
//1:定义出口
if(left >= right) return;
//2:把数组分成两个区间 [left,mid] [mid+1,right]
int mid = (left + right)/2;
//3:把左边区间排个序,再把右边区间排个序
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//4:合并排序好的两个区间
int cur1 = left , cur2 = mid + 1 , i = 0;
while(cur1 <= mid && cur2 <= right){
tem[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while(cur1 <= mid) tem[i++] = nums[cur1++];
while(cur2 <= right) tem[i++] = nums[cur2++];
// 5:将tem中的值copy给nums
for(int j = left ; j <= right ; j++){
nums[j] = tem[j-left];
}
}
}
易错点:ret的定义
class Solution {
int[] tmp;//全局变量节约资源
public int reversePairs(int[] record) {
// 利用归并排序解决问题
int n = record.length;
tmp = new int[n];
return mergeSort(record,0,n-1);
}
public int mergeSort(int[] nums , int left , int right){
if(left >= right){
return 0;
}
int ret = 0;//用来存储逆序对的个数
// 1:选择一个中间节点,将数组划分为两个部分
int mid = (left + right)/2;
// [left,mid][mid+1,right]
// 2:左半部分的个数 + 排序 + 右边部分的个数 + 排序
ret += mergeSort(nums,left,mid);
ret += mergeSort(nums,mid+1,right);
// 3:一左一右的个数
// 定义双指针
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++];
}
}
// 4:处理排序
//先处理一下没有排完的元素
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;
}
}
降序
while(cur1 <= mid && cur2 <= right){
if(nums[cur1] <= nums[cur2]){ //试一下用大的部分在右半部分中找(降序)
tmp[i++] = nums[cur2++];
}else{
ret += right - cur2 + 1;
tmp[i++] = nums[cur1++];
}
}
这道题的几个重点
1:中间数组需要创建两个,一个放元素,一个放元素的下标
2:创建结果数组ret,在归并的时候,ret是+=因为可能在归并过程中ret数组需要更新的那个位置本身就有值
3:数组一定是呈现为降序排列
易错点:
1:在第一遍写这个代码的时候,没有注意到下标也需要创建一个中间数组,最后也需要合并更新
2:for循环注意,写代码的时候不要图快,稳最重要。
3:降序排列,找比当前元素小的元素,是去右边数组中找那一堆
class Solution {
int[] index;
int[] ret;
int[] tmp;// 中间数组得搞两个分别记录数值和下标
int[] tmpIndex;
public List<Integer> countSmaller(int[] nums) {
// 这道题的核心在于,需要的原下标下更改数值,创建一个index数组保存下标
// 准备工作
int n = nums.length;
tmp = new int[n];
index = new int[n];
ret = new int[n];
tmpIndex = new int[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
mergeSort(nums, 0, n - 1);
List<Integer> l = new ArrayList<>();
for (int j = 0; j < n; j++) {
l.add(ret[j]);
}
return l;
}
public void mergeSort(int nums[], int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// [left , mid] [mid + 1 , right];
int cur1 = left, cur2 = mid + 1, i = 0;// 降序
while (cur1 <= mid && cur2 <= right) {
if (nums[cur1] > nums[cur2]) {
tmp[i] = nums[cur1];
ret[index[cur1]] += right - cur2 + 1; // 可能原来的位置上已经有数值了,所以是+=
tmpIndex[i++] = index[cur1++];
} else if (nums[cur1] <= nums[cur2]) {
tmp[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];// 记录这个元素原来的下标,放到中转下标数组中
}
}
while (cur1 <= mid) {
tmp[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while (cur2 <= right) {
tmp[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
// 合并数组(元素和下标都要合并)
for (int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
index[j] = tmpIndex[j - left];
}
}
}
核心问题不在于比较,而在于不成立时,加入tmp数组中就不是降序或者升序了,下面举例展示
上面通过举例左半部分【7,9,10】右半部分【3,4】说明了升序不能找到一个就直接找到一堆这样的算法,我来解释,例如 7 > 2*3 因为是升序所以去左边统计 共计有7,9,10三个符合条件的数字,7统计完,放入tmp中间数组中(tmp本应也是升序数组tmp【3】)右指针移动到4,此时,7<2*4条件不满足,按照程序逻辑,不满足就把7扔进tmp,然后移动指针到9。tmp【3,7】,继续按照逻辑执行9>4*2,此时可以找到一堆9和10,两个符合条件。然后把4扔进tmp【3,7,4】出问题了,tmp不是升序的了。
同理降序也是这个问题,这就是这道题核心的本质。需要把排序统计和合并数组两个逻辑分开处理的原因
我明白了,为什么不能沿用计算右侧小于当前元素的个数这个题的思路,而要把比较和排序两个逻辑分开,举例如下。最核心的一点是比较的逻辑被破坏了,可能左边【10】 , 右边【8,4,1】
class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right) {
// 函数出口
if (left >= right) {
return 0;
}
// 划分两部分[left,mid][mid+1,right]
int mid = (left + right) / 2;
int ret = 0; // ret统计最后结果
// 统计左边部分的翻转对,在统计右边的
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 统计一左一右两部分-核心逻辑
// 定义双指针,以降序为例
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
if (nums[cur1]/2.0 <= nums[right]) {
break;
}
while (cur2 <= right && nums[cur1]/2.0 <= nums[cur2]) {
cur2++;
}
ret += right - cur2 + 1;
cur1++;
}
// 合并排序好的两个部分
cur1 = left;
cur2 = mid + 1;
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++];
}
for (int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
return ret;
}
}
class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right) {
// 函数出口
if (left >= right) {
return 0;
}
// 划分两部分[left,mid][mid+1,right]
int mid = (left + right) / 2;
int ret = 0; // ret统计最后结果
// 统计左边部分的翻转对,在统计右边的
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 统计一左一右两部分-核心逻辑
// 定义双指针,以升序为例
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
if (nums[mid]/2.0 <= nums[cur2]) {
break;
}
while (cur1 <= mid && nums[cur1]/2.0 <= nums[cur2]) {
cur1++;
}
ret += mid - cur1 + 1;
cur2++;
}
// 合并排序好的两个部分
cur1 = left;
cur2 = mid + 1;
while (cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] > nums[cur2] ? nums[cur2++] : 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;
}
}