LeetCode-剑指Offer_剑指offer leetcode

---

包含main函数的栈

一、题目描述
LeetCode-剑指 offer30.包含main函数的栈

二、分析与代码
分析

第一个想到的思路：
1、申请两个栈S1、S2，将输入数据push到S1中。
2、当要输出S1中最小数据时，将数据从S1中pop出，并依次push到S2中，同时记录最小值。
3、之后再将数据从S2中pop出push到S1中。
以上操作后在S1中的数据顺序并未改变，并且可以正常实现功能，但是时间复杂度过高，会导致超时，具体代码如代码1。

改进思路：
1、申请两个栈S1、S2，将输入数据push到S1中，并在push数据的同时在S2中记录到此数据为止S1中数据的最小值，并将最小值同步push到S2中。
2、每次pop数据时，S1、S2同时要pop。
3、输出S1中的最小值只需要输出S2的栈顶元素即可。
具体代码如代码2。

具体代码

代码1：

class MinStack {
public:
    stack <int> Stack;
    stack <int> Stack2;

    MinStack() {
        while(!Stack.empty())
            Stack.pop();
        while(!Stack2.empty())
            Stack2.pop();
    }
    
    void push(int x) {
        Stack.push(x);
    }
    
    void pop() {
        Stack.pop();
    }
    
    int top() {
        return Stack.top();
    }
    
    int min() {
        int ans=Stack.top();
        while(!Stack.empty())
        {
            Stack2.push(Stack.top());
            if(ans>Stack.top())
                ans=Stack.top();
            Stack.pop();
        }
        while(!Stack2.empty())
        {
            Stack.push(Stack2.top());
            Stack2.pop();
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

代码2：

class MinStack {
public:
    stack <int> Stack;
    stack <int> Stack2;
   
    MinStack() {
        while(!Stack.empty())
            Stack.pop();
        while(!Stack2.empty())
            Stack2.pop();
        Stack2.push(INT_MAX);
    }
    
    void push(int x) {
        Stack.push(x);
        if(x<Stack2.top())
            Stack2.push(x);
        else
            Stack2.push(Stack2.top());
    }
    
    void pop() {
        Stack.pop();
        Stack2.pop();
    }
    
    int top() {
        return Stack.top();
    }
    
    int min() {
        return Stack2.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

复杂链表的复制

一、题目描述
LeetCode-剑指 offer35.复杂链表的复制

二、分析与代码
分析

第一种思路：
1、将初始链表的每一个结点拆分为两个结点，例如将A->B->C复制为A->A’->B->B’->C->C’。主要为：将A的内容复制到A’，A的next指针指向A’，A’的next指针指向B，random指针不设置。
2、设置random指针的指向，例如：A的random指针指向D，我们就要将A’指针指向D’，方法为：将A’的random指针指向A的random指针指向的D的next指针指向的D’。
3、将复制的A->A’->B->B’->C->C’拆分为A->B->C与A’->B’->C’，将A’->B’->C’的头指针返回。
具体代码如代码1。

第二种思路：
由复制可想到用map <typename1,typename2> name来复制链表，例如：初始链表为A->B->C，复制链表为A’->B’->C’，A与A’对应……，则用name[A]=A’来设置A与A’的对应关系。具体代码如代码2。

具体代码

代码1：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        //为空返回
        if(head==NULL)
            return NULL;
        //将A->B->C复制为A->A'->B->B'->C->C'
        for(Node *q=head;q!=NULL;q=q->next->next)
        {
            Node *p=new Node(q->val);
            p->next=q->next;
            q->next=p;
        }
        //将复制后的A->A'->B->B'->C->C'其中A、B、C的random指针复制到A'、B'、C'上
        for(Node *q=head;q!=NULL;q=q->next->next)
            if(q->random!=NULL)
                q->next->random=q->random->next;
        Node *newhead=head->next;
        //将A->A'->B->B'->C->C'拆分为A->B->C与A'->B'->C'，A->B->C为原链表，A'->B'->C'为复制链表
        for(Node *p=head;p!=NULL;p=p->next)
        {
            Node *mid=p->next;
            p->next=p->next->next;
            if(mid->next!=NULL)
                mid->next=mid->next->next;
        }
        return newhead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

代码2：

class Solution {
public:
    map<Node*, Node*> cachedNode;
    Node* copyRandomList(Node* head) {
        //为空返回
        if(head==NULL)
            return NULL;
        //不包含则创建
        if (!cachedNode.count(head)){
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

对称的二叉树

一、题目描述
LeetCode-剑指 offer28.对称的二叉树

二、分析与代码
分析
判断一棵树是否为对称的二叉树，只需要判断该树根结点的左子树与右子树是否关于根结点对称，具体步骤如下：
1、特殊情况：若该树为空，则返回true；
2、对该树根结点的左右子树进行递归判断，共有以下情况：（1）若左子树与右子树都不存在，则左子树与右子树对称，返回true；（2）若左、右子树只有一个存在，则左、右子树不对称，返回false；（3）若左右子树都存在，则返回q->val==p->val（左右子树根结点值比较）&&check(p->left,q->right)（左子树的左结点与右子树的右结点比较）&&check(p->right,q->left)（右子树的左结点与左子树的右结点比较）。
具体代码如下：

具体代码

代码：

class Solution {
public:
    bool check(TreeNode *p,TreeNode *q){
        if(!p&&!q)
            return true;
        if(!p||!q)
            return false;
        return q->val==p->val&&check(p->left,q->right)&&check(p->right,q->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL)  
            return true;
        return check(root->left,root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

两个链表的第一个公共结点

一、题目描述
LeetCode-剑指 offer52.两个链表的第一个公共结点

二、分析与代码
分析
设链表link1的结点数为l1+c，link2的结点数为l2+c，c则为两链表公共部分的长度。则可有以下思路：
1、设p指向link1的表头，q指向link2的表头；
2、p与q同时向后移动，当p遍历完link1时使其指向link2的表头，当q遍历完link2时使其指向link1的表头，并使p，q继续同时向后移动；
3、当p、q指向同一结点时，该结点就是两链表的第一个公共点（因为此时p遍历了l1+c+l2个结点，q遍历了l2+c+l1个结点，遍历的结点数相同，二者指向的都是公共部分c的第一个结点）。
具体代码如下：

具体代码

代码1：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *node1 = headA;
        ListNode *node2 = headB;
        
        while (node1 != node2) 
        {
            if(node1!=NULL)
                node1=node1->next;
            else
                node1=headB;
            if(node2!=NULL)
                node2=node2->next;
            else    
                node2=headA;
        }
        return node1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码2：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL)    
            return NULL;
        ListNode *p=headA,*q=headB;
        while(p!=NULL&&q!=NULL&&p!=q)
        {
            p=p->next;
            q=q->next;
        }
        if(p==q)
            return p;
        if(p==NULL)
        {
            p=headB;
            while(q!=NULL)
            {
                p=p->next;
                q=q->next;
            }
            q=headA;
            while(p!=NULL&&q!=NULL&&p!=q)
            {
                p=p->next;
                q=q->next;
            }
            if(p==q)
                return p;
            return NULL;
        }
        if(q==NULL)
        {
            q=headA;
            while(p!=NULL)
            {
                p=p->next;
                q=q->next;
            }
            p=headB;
            while(p!=NULL&&q!=NULL&&p!=q)
            {
                p=p->next;
                q=q->next;
            }
            if(p==q)
                return p;
            return NULL;
        }
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

把数组排成最小的数

一、题目描述
LeetCode-剑指 offer45.把数组排成最小的数

二、分析与代码
分析
要将nums利用类似冒泡排序排列(将两数字x，y拼接字符串x+y与y+x，比较它们的大小)，之后将nums数组按序拼接起来即可。

具体代码

代码：

class Solution {
public:
    int num(int x){
        if(x==0)
            return 1;

        int ans=0;
        while(x)
        {
            ans++;
            x=x/10;
        }
        return ans;
    }

    bool compare(int x,int y){
        if(x*pow(10,num(y))+y>x+y*pow(10,num(x)))
            return true;
        return false;
    }

    string minNumber(vector<int>& nums) {
        for(int i=0;i<nums.size()-1;i++)
            for(int j=0;j<nums.size()-i-1;j++)
                if(compare(nums[j],nums[j+1]))
                {
                    int x=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=x;
                }
        
        string ans;
        vector<int> a;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==0)
                ans.push_back('0');
            else
            {
                a.clear();
                int x=nums[i];
                while(x)
                {
                    a.push_back(x%10);
                    x/=10;
                }
                reverse(a.begin(),a.end());
                for(int j=0;j<a.size();j++)
                    ans.push_back('0'+a[j]);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

数据流中的中位数

一、题目描述
LeetCode-剑指 offer41.数据流中的中位数
LeetCode-295.数据流中的中位数
二、分析与代码
分析
剑指 offer41：
该题对时间复杂度要求较低，故可用以下方法：
1、定义一个vector<int> a，用来存放所有的数字；
2、在加入数字时，利用二分法找到数字该插入的位置，将数字插入；
3、按对应的中位数的定义输出中位数。
具体代码如代码1。

对于LeetCode-295，以上方法时间复杂度较高，会引起超时。故需转用以下方法：
1、定义两个优先队列que_Min、que_Max。其中que_Min用来存储较小的一半数字，使用默认比较方式，top()方法返回最大值；que_Max用来存储较大的一半数字，使用greater<>比较方式，top()返回最小值；
2、在加入数字数，当que_Min.empty()||num<=que_Min.top()时，num一定是插入que_Min中，插入后，若que_Min.size()-1>que_Max.size()，则将que_Min中的最大值移入que_Max中；当!que_Min.empty()&&num>que_Min.top()时，num一定插入que_Max中，插入后，若que_Max.size()>que_Min.size()，则将que_Max中的最小值移入que_Min中；
3、若que_Min.size()==que_Max.size()，则取出que_Min.top()与que_Max.top()求和除以2；否则输出que_Min.top()即可。

具体代码

代码1：

class MedianFinder {
public:
    vector<int> a;
    MedianFinder() {
        a.clear();
    }

    void addNum(int num) {
        //特例
        if(a.size()==0||a[a.size()-1]<=num)
        {
            a.push_back(num);
            return;
        }
        if(a[0]>=num)
        {
            a.insert(a.begin(),num);
            return;
        }

        //二分法找到插入位置
        int x;
        int left=0,right=a.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(a[mid]>=num&&a[mid-1]<=num)
            {
                x=mid;
                break;
            }
            if(a[mid]<num)
                left=mid+1;
            else
                right=mid-1;
        }
        a.insert(a.begin()+x,num);
    }
    
    double findMedian() {
        double ans;
        int n=a.size();
        if(a.size()%2==0)
            ans=(double)(a[n/2]+a[n/2-1])/2.0;
        else
            ans=(double)a[n/2];
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

代码2：

class MedianFinder {
public:
    priority_queue<int,vector<int>,greater<>> que_Max;  //greater<>方法使优先队列队头返回最小值
    priority_queue<int,vector<int>> que_Min;

    MedianFinder() {
        //初始化，将队列处理空
        while(!que_Max.empty())
            que_Max.pop();
        while(!que_Min.empty())
            que_Min.pop();
    }
    
    void addNum(int num) {
        if(que_Min.empty()||num<=que_Min.top())
        {
            que_Min.push(num);
            if(que_Min.size()-1>que_Max.size())
            {
                que_Max.push(que_Min.top());
                que_Min.pop();
            }
        }
        else
        {
            que_Max.push(num);
            if(que_Max.size()>que_Min.size())
            {
                que_Min.push(que_Max.top());
                que_Max.pop();
            }
        }
    }
    
    double findMedian() {
        if(que_Max.size()==que_Min.size())
            return (que_Min.top()+que_Max.top())/2.0;
        return que_Min.top()/1.0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

求1+2+…+n

一、题目描述
LeetCode-剑指 offer64. 求1+2+…+n

二、分析与代码
分析
若无题目中的限制要求，我们可用递归实现1+2+……+n，代码如下：

class Solution {
public:
    int sumNums(int n) {
        if(n==0)
            return 0;
        return n+sumNums(n-1);
    }
};
1
2
3
4
5
6
7
8

但是题目中要求不允许使用if，则我们需要考虑如何代替掉if，自然可想到&&，具体如下：
1、使用n&&A，当n=0时，不会执行A，则可模拟if的效果（如果n!=0，则执行A，否则不执行A）。
2、当n=0时返回0，即返回n也可；n!=0时返回n+sumNums(n-1)，则将n+sumNums(n-1)赋值给n，也是返回n，故A可写为n+=sumNums(n-1)。
3、返回n即可。
具体代码如下：

具体代码

代码：

class Solution {
public:
    int sumNums(int n) {
        n&&(n+=sumNums(n-1));
        return n;
    }
};
1
2
3
4
5
6
7

二叉树的最近公共祖先

一、题目描述
LeetCode-剑指 offer68.二叉树的最近公共祖先

二、分析与代码
分析
二叉树两个结点的最近公共祖先满足以下条件之一：（1）左子树与右子树分别包含一个结点；（2）左子树或右子树包含一个结点，且本身就是一个结点；（3）两结点相同且本身就是这两个结点。
故可采用以下思路：
1、定义一指针ans用以指向答案；
2、定义bool型函数dfs，当以root为根的树包含p或q结点时，返回true，否则返回false；
3、在dfs中用ll与rr记录root的左右子树是否包含p或q结点；当root为空时dfs返回false，当ll为true或rr为true或root本身就是结点之一时，返回true；
4、若ll&&rr或root==p&&root==q或(ll||rr)&&(root==p||root==q)，则说明root为所求结点，用ans记录；（注意：满足这些条件之一的结点只有一个，故ans不会重复赋值）。
具体代码如下：

具体代码

代码：

class Solution {
public:
    TreeNode *ans;
    //检查root为根的树是否最少包括p、q之一
    bool dfs(TreeNode *root,TreeNode *p,TreeNode *q){
        if(root==NULL)
            return false;
        bool ll=dfs(root->left,p,q);
        bool rr=dfs(root->right,p,q);
        if((ll&&rr)||(root==p&&root==q)||((ll||rr)&&(root==p||root==q)))
            ans=root;
        return ll||rr||(root==p||root==q);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

不用加减乘除做加法

一、题目描述
LeetCode-剑指 offer65.不用加减乘除做加法

二、分析与代码
分析
该题不允许用加减乘除做加法，故自然想到运用位运算：
1、将a与b做与运算，运算结果左移一位，再保存到c中，c就是a与b求和的进位；
2、将a与b做异或运算，并将结果保存在a中，a就是a与b求和未考虑进位的结果；
3、此时只需要将a与c相加即可，但是该题不允许用加法，故只能将c赋值给b重复以上步骤，直到进位为0返回a即可。
具体代码如下：

具体代码

代码：

class Solution {
public:
    int add(int a, int b) {
        while(b!=0)
        {
            int c=(unsigned)(a&b)<<1;//进位无负数情况
            a^=b;
            b=c;
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

二叉搜索树的后序遍历序列

一、题目描述
LeetCode-剑指 offer33.二叉搜索树的后序遍历序列

二、分析与代码
分析
后序遍历的最后一个元素是根结点，二叉搜索树的左子树小于根结点小于右子树，故可有以下思路：
1、最后一个元素为根结点，从左往右遍历，找出左子树结点（即值比根结点小的）；
2、验证右子树是否元素值都大于根结点，若存在小于根结点的元素值，则返回false；
3、递归验证左右子树是否都为二叉搜索树，若是，则返回true（即返回左右子树结果的&&）。
具体代码如下：

具体代码

代码：

class Solution {
public:
    bool check(vector<int>postorder,int left,int right){
    	//只有一个结点，一定为二叉搜索树
        if(left>=right)
            return true;
        int mid;
        for(mid=left;postorder[mid]<postorder[right]&&mid<right;mid++);
        for(int i=mid;i<right;i++)
            if(postorder[i]<postorder[right])
                return false;
        return check(postorder,left,mid-1)&&check(postorder,mid,right-1);
    }

    bool verifyPostorder(vector<int>& postorder) {
        return check(postorder,0,postorder.size()-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

构建乘积数组

一、题目描述
LeetCode-剑指 offer66.构建乘积数组

二、分析与代码
分析
思路1：
将数组所有的数做乘法运算，结果记为n，之后遍历数组，当遍历到第i个时，记录n/a[i]的值即可。但是本题不允许用除法。

思路2：
直接遍历数组，当遍历到第i个时，将i前所有数与i后所有数做乘法运算，记录结果即可，但是时间复杂度大，会造成超时。

思路3：
将思路2进行改进：
1、定义vector<int> left, right，将数组的前i个数与后i个数的乘积分别记录到left与right中。
2、遍历数组，当遍历到第i个时只需要用left与right中的对应数相乘即可。
具体代码如下：

具体代码

代码：

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> ans,left,right;
        if(a.size()==0)
            return ans;
        int l=1,r=1;
        for(int i=0;i<a.size();i++)
        {
            l*=a[i];
            left.push_back(l);
            r*=a[a.size()-1-i];
            right.push_back(r);
        }
        ans.push_back(right[a.size()-2]);
        for(int i=1;i<a.size()-1;i++)
            ans.push_back(left[i-1]*right[a.size()-i-2]);
        ans.push_back(left[a.size()-2]);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

圆圈中最后剩下的数字

一、题目描述
LeetCode-剑指 offer62.圆圈中最后剩下的数字

二、分析与代码
分析
本题是著名的“约瑟夫环”问题，可使用动态规划解决。
首先说明lastRemaining(n,m)函数的返回值为0到n-1共n个数组成的首尾相连的数字环进行操作——删除第m个数，从删除的数的下一个数开始计数，再删除第m个数，直到剩下最后一个数的值。
思路如下：
1、设lastRemaining(n-1,m)=x，即从0到n-2共n-1个数进行以上操作后剩下的值为x，则说明lastRemaining(n-1,m)剩下的是第x+1个数。
2、lastRemaining(n,m)首先删除的是第m%n个数，之后从第m%n个数的下一个数开始计数，计数到第m个为需要删除的数字。该过程可等同于：当删除了第m%n个数字后，数的量为n-1（刚开始有n个减去了1个），之后将第m%n个数后的数字放到数列前方，就可以从第一个开始重新计数，这也就转换成了lastRemaining(n-1,m)的情况（注意：lastRemaining(n-1,m)中的数对应的是0到n-2共n-1个数，但是由lastRemaining(n,m)删除一个数字后对应的lastRemaining(n-1,m)中的数却不是0到n-2）；
3、已知lastRemaining(n-1,m)=x，即lastRemaining(n-1,m)剩下的是第x+1个数。则lastRemaining(n,m)返回的数就是由lastRemaining(n,m)删除一个数字后对应的lastRemaining(n-1,m)中的第x+1个数，即在lastRemaining(n,m)中的(m%n+x+1)%n个数，值为(m%n+x)%n=(m+x)%n，则可得lastRemaining(n,m)=(m+lastRemaining(n-1,m))%n。
具体代码如下：

具体代码

代码：

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n==1)
            return 0;
        int x=lastRemaining(n-1,m);
        return (x+m)%n;
    }
};
1
2
3
4
5
6
7
8
9

滑动窗口的最大值

一、题目描述
LeetCode-剑指 offer59.I.滑动窗口的最大值

二、分析与代码
分析
思路1:
可用暴力法将每个窗口的k个元素遍历，记录其中最大值，共n-k+1个窗口。该方法的时间复杂度过大，会超时。

思路2:
对于思路1的暴力法，我们可以发现每两个相邻的窗口之间有k-1个数字是相同的，只是删除了前一窗口中的第一个值，加入了后一窗口的最后一个值，故后一窗口的最大值可借助上一窗口的比较情况得出（对前一窗口加入后一窗口的最后一个值，之后找到最大值，保证最大值的下标是在后一窗口内即可，故需使用pair方便存储值及对应下标），可以使用优先队列比较和存储值的大小情况。具体如下：
1、申请一个priority_queue，队列元素为pair<int,int>，名称为a，存储值的大小及下标；申请vector ans，存储满足条件值；
2、将前k个数的信息存储进优先队列中，并保存a.top()的值到ans中（优先队列默认比较方式的top输出最大值）；
3、从下标为k的元素开始依次加入到a中，每加入一个数，都判断a.top()的下标是否在窗口内，若不在，则删除，若在，则保存到ans中。
具体代码如下：

具体代码

代码：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        //特殊情况
        if(nums.size()<k||k==0)
            return ans;
            
        priority_queue<pair<int,int>> a;
        for(int i=0;i<k;i++)
            a.push({nums[i],i});
        ans.push_back(a.top().first);
        for(int i=k;i<nums.size();i++)
        {
            a.push({nums[i],i});
            while(a.top().second<=i-k)
                a.pop();
            ans.push_back(a.top().first);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

数组中的逆序对

一、题目描述
LeetCode-剑指 offer51.数组中的逆序对

二、分析与代码
分析
见到逆序对就要想到归并排序！！！
见到逆序对就要想到归并排序！！！
见到逆序对就要想到归并排序！！！

可通过对原数组进行归并排序来计算原数组的逆序对。
具体代码如下：

具体代码

代码：

class Solution {
public:
    int ans=0;
    //nums修改后需要进行更新，别忘了加&
    void mergesort(vector<int>& nums,int left,int right){
        if(left>=right)
            return;
        int mid=(left+right)/2;
        mergesort(nums,left,mid);
        mergesort(nums,mid+1,right);
        int b[right-left+1],a=0,i=left,j=mid+1;   
        while(i<=mid&&j<=right)
            if(nums[i]>nums[j])
            {
                b[a++]=nums[j++];
                //只需在将后半部分的数放在前面时计算该数后有几个前半部分数
                ans+=mid-i+1;
            }
            else
                b[a++]=nums[i++];
        while(i<=mid)
            b[a++]=nums[i++];
        while(j<=right)
            b[a++]=nums[j++];
        for(int i=0;i<right-left+1;i++)
            nums[left+i]=b[i];
    }

    int reversePairs(vector<int>& nums) {
        mergesort(nums,0,nums.size()-1);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

一、题目描述
LeetCode-剑指 offer

二、分析与代码
分析

具体代码

代码：

1