leetcode 493 Reverse Pairs-白红宇

leetcode 493 Reverse Pairs

阅读量：5323 次

发布时间：2019-06-14

本文共 2444 字，大约阅读时间需要 8 分钟。

题意：给定一个数组nums，求若 i<j and nums[i] > 2*nums[j] 的逆序对。

Note: 数组的长度不会超过50，000

不愧是hard模式的题目，虽然已经知道可以用归并排序来做，但是写出来的答案总有问题，真的是暴风哭泣 :(

一直在找bug，最后发现是我写的merge函数有问题，分析一下：

这是我一开始写的错误的merge函数，我是在 aux[i] > aux[j] 里面加入了若也满足 aux[i] > 2*aux[j] 来计算res

int merge(vector
     
      & arr, vector
      
       & aux, int l, int mid, int r){        for(int i=l;i<=r;i++){            aux[i] = arr[i];        }        int res = 0;   //统计逆序对数量        int i = l, j = mid+1;        for(int k=l; k<=r;k++){            if(i>mid){                arr[k] = aux[j];                j++;            }            else if(j>r){                arr[k] = aux[i];                i++;            }            else if(aux[i]
       
         2*aux[j])                    res+=(mid-i+1); 　　　　　　　　　 j++;            }        }        return res;    }

我一直不知道自己的解法为什么不对，然后参考了别人的解法，改了一下merge函数。

我觉得错误的地方是把 if(aux[i] > 2*aux[j]) 这个语句放在了 aux[i] > aux[j] 里，只有当同时满足这两个条件时res才会增加，但是若不满足2倍的大于关系时，j++ , 这样就会丢掉一些解。所以要把它拿出来另外判断！

正确解法如下：

class Solution {public:    int mergeSort(vector
     
      & nums, vector
      
       & aux, int l, int r){        if(l >= r) return 0;        int mid = (l+r)/2;   //(l+r)>>1        int left = mergeSort(nums, aux, l, mid);        int right = mergeSort(nums, aux, mid+1,r);        int pair = left + right + merge(nums, aux, l, mid, r);        return pair;    }        int merge(vector
       
        & arr, vector
        
         & aux, int l, int mid, int r){        for(int i=l;i<=r;i++){            aux[i] = arr[i];        }                int res = 0;   //统计逆序对数量        int i = l, j = mid+1;        for(int k=l; k<=r;k++){            if(i>mid){                arr[k] = aux[j];                j++;            }            else if(j>r){                arr[k] = aux[i];                i++;            }            else if(aux[i]
         
           2LL*aux[t]){                res += mid-s+1;                t++;            }          }*/        for(int s=l,t=mid;s<=mid;s++){            while(t+1<=r && aux[s] > 2LL*aux[t+1]) t++;            res += t-mid;   // t-(mid+1)+1 = t-mid        }                return res;    }        int reversePairs(vector
          
           & nums) { int n = nums.size(); if(n==0) return 0; vector
           
             aux(nums); return mergeSort(nums, aux, 0, n-1); }};

hard模式真是不容易 == 刷题真难 ? 努力努力

转载于:https://www.cnblogs.com/Bella2017/p/10143825.html

你可能感兴趣的文章