首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++版 - 剑指Offer 面试题36:数组中的逆序对及其变形(Leetcode 315. Count of Smaller Numbers After Self)题解

C++版 - 剑指Offer 面试题36:数组中的逆序对及其变形(Leetcode 315. Count of Smaller Numbers After Self)题解

作者头像
Enjoy233
发布2019-03-05 14:32:15
1.3K0
发布2019-03-05 14:32:15
举报

剑指Offer 面试题36:数组中的逆序对

题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

例如, 在数组{7,5,6,4}中,一共存在5个逆序对,分别是(7,6),(7,5),(7,4),(6,4)和(5,4),输出5.

提交网址: http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=11188

http://ac.jobdu.com/problem.php?pid=1348

输入:

每个测试案例包括两行:

第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。

第二行包含n个整数,每个数组均为int类型。

输出:对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。样例输入:4 7 5 6 4样例输出:5

分析:

逆序对(Inversion Pairs)的定义:

a[i] < a[j] and i > j, 那么a[i] 和 a[j]就是一个逆序对。求逆序对的总数就是给出一组数字, 要求计算出这个数列里面的逆序对的数量.

以数组{7, 5, 6, 4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候,我们不能拿它和后面的每一个数字作比较,否则时间复杂度就是O(n^5),因此我们可以考虑先比较两个相邻的数字。

  如图5.1 (a)和图5.1 (b)所示,先把数组分解成两个长度为2的子数组, 再把这两个子数组分别拆分成两个长度为1的子数组。接下来一边合并相邻的子数组, 一边统计逆序对的数目。在第一对长度为1 的子数组{7}、{5}中7大于5 ,因此(7, 5)组成一个逆序对。同样在第二对长度为1 的子数组{6}、{4}中也有逆序对(6, 4)。由于我们已经统计了这两对子数组内部的逆序对,因此需要把这两对子数组排序(图5.1 (c)所示),以免在以后的统计过程中再重复统计。

逆序对总数count=leftCount+rightCount+crossCount

注:图中省略了最后一步, 即复制第二个子数组最后剩余的4到辅助数组中.  (a) P1指向的数字大于P2指向的数字,表明数组中存在逆序对. P2指向的数字是第二个子数组的第二个数字,因此第二个子数组中有两个数字比7小.  把逆序对数目加2,并把7 复制到辅助数组,向前移动P1和P3. (b) P1指向的数字小子P2指向的数字,没有逆序对. 把P2指向的数字复制到辅助数组,并向前移动P2和P3.  (c) P1指向的数字大于P2指向的数字,因此存在逆序对.  由于P2指向的数字是第二个子数组的第一个数字,子数组中只有一个数字比5小.  把逆序对数目加1,并把5复制到辅助数组,向前移动P1和P3 .

       接下来我们统计两个长度为2 的子数组之间的逆序对。我们在图5.2 中细分图5.1(d)的合并子数组及统计逆序对的过程。    我们先用两个指针分别指向两个子数组的末尾,并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个子数组中的数字,则构成逆序对,并且逆序对的数目等于第二个子数组中剩余数字的个数(如图5.2(a)和图5.2(c)所示)。如果第一个数组中的数字小于或等于第二个数组中的数字,则不构成逆序对(如图5.2(b)所示)。每一次比较的时候,我们都把较大的数字从后往前复制到一个辅助数组中去,确保辅助数组中的数字是递增排序的。在把较大的数字复制到辅助数组之后,把对应的指针向前移动一位,接下来进行下一轮比较。    经过前面详细的讨论, 我们可以总结出统计逆序对的过程先把数组分隔成子数组, 先统计出子数组内部的逆序对的数目,然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中,还需要对数组进行排序。如果对排序算法很熟悉,我们不难发现这个排序的过程实际上就是归并排序。

代码:

#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
int InversePairs(vector<int> data)
    {
        int len = data.size();
        if(len==0) return 0;        
        return getCount(data, 0, len-1);
    }
int getCount(vector<int>& data, int begin, int end)  // 这里data需要用&进行引用传值
{
        if(begin >= end) return 0;         // 递归终止条件
        int mid = (begin + end)/2;
        int lCount = getCount(data, begin, mid);   // 递归,归并排序,并计算本次逆序对数 
        int rCount = getCount(data, mid+1, end);         
        vector<int> temp=data; // 辅助数组,用于归并排序
        int forIdx=mid, backIdx=end, tempIdx=end;  // forIdx:前半部分的下标,backIdx:后半部分的下标,tempIdx:辅助数组的下标       
        int crossCount = 0;    // 记录交叉的逆序对数
        while(forIdx>=begin && backIdx >= mid+1)
        {
            if(data[forIdx] > data[backIdx])   // 存在交叉的逆序对,先统计一下,然后依次将较大值放进辅助数组
            {
                temp[tempIdx--] = data[forIdx--];
                crossCount += backIdx - mid;
            } else {
                temp[tempIdx--] = data[backIdx--];  // 不存在交叉的逆序对,依次将较大值放进辅助数组 
            }
        }
        while(forIdx >= begin)
            temp[tempIdx--] = data[forIdx--];
        while(backIdx >= mid+1)
            temp[tempIdx--] = data[backIdx--];
        for(int i=begin; i<=end; i++)
            data[i] = temp[i]; 
        return (lCount+rCount+crossCount);
    }
 };
// 以下为测试部分
int main()
{
    Solution sol;
    vector<int> vec1={8,4,2,7,6,2};
    vector<int> vec2={1,2,3,9,8,7,6};
    vector<int> vec3={7,5,6,4};     
    int num1=sol.InversePairs(vec1);
    int num2=sol.InversePairs(vec2);
    int num3=sol.InversePairs(vec3);
    
    printf("%d\n",num1); 
    printf("%d\n",num2);
    printf("%d\n",num3);            
    return 0;
}

牛客网AC代码:

class Solution {
public:    
    long getCount( vector<int> &data, vector<int> &copy, long start, long end){
        if(start == end)  // copy: 辅助数组
        {
            return 0 ;  // 递归终止条件
        }        
        long mid = (start + end)/ 2 ;
        long lCount = getCount(copy, data, start, mid); // 递归,归并排序,并计算本次逆序对数 
        long rCount = getCount(copy, data, mid+1, end);
        long crossCount = 0 ;       // 记录交叉的逆序对数
        long i = mid, j = end, tempIdx = end;  //i:前半部分的下标,j:后半部分的下标,tempIdx:辅助数组的下标
        
        while(i >= start && j > mid) {   // 存在交叉的逆序对,先统计一下,然后依次将较大值放进辅助数组
            if (data[i] > data[j]) {   
                copy[tempIdx--] = data[i--];
                crossCount += j - start - (mid-start);
            } else {
                copy[tempIdx--] = data[j--];   // 不存在交叉的逆序对,依次将较大值放进辅助数组 
            }
        }
        while(i >= start) {
            copy[tempIdx--] = data[i--];
        }
        while(j > mid) {
            copy[tempIdx--] = data[j--];
        }        
        return (lCount + rCount + crossCount) % 1000000007; //数值过大时求余, 防止溢出
    }
    
    int InversePairs(vector<int> &data) {
        if(data. size () == 0 ) return 0 ;
        else if (data. size() == 1 ) return 1 ;
        else {
            vector<int> copy(data);
            return getCount(data, copy, 0 , data.size()- 1);
        }
    }
};

315. Count of Smaller Numbers After Self

Total Accepted: 9951 Total Submissions: 32512 Difficulty: Hard

提交网址:  https://leetcode.com/problems/count-of-smaller-numbers-after-self/

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

AC代码:

<pre name="code" class="cpp">class Solution {
    vector<pair<int, int> > x;
    vector<int> ans;
public:
    vector<int> countSmaller(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++)
                x.push_back(make_pair(nums[i], i));
        ans = vector<int>(x.size(), 0);
        merge_sort(0, x.size() - 1);
        return ans;
    }

    void merge_sort(int start, int end) {
        if (end <= start) return;
        int mid = start + (end - start) / 2;
        merge_sort(start, mid);
        merge_sort(mid + 1, end);
        merge(start, mid, mid + 1, end);
    }

    void merge(int start1, int end1, int start2, int end2) {
        vector<pair<int, int> > tmp;
        int p = start1, q = start2;
        while (p <= end1 && q <= end2) {
            if (x[p].first <= x[q].first) {
                ans[x[p].second] += q - start2;
                tmp.push_back(x[p++]);
            } else {
                tmp.push_back(x[q++]);
            }
        }
        while (p <= end1) {
            ans[x[p].second] += q - start2;
            tmp.push_back(x[p++]);
        }
        while (q <= end2) tmp.push_back(x[q++]);
        for (int i = start1; i<= end2; i++) x[i] = tmp[i - start1];
    }
};

99. Recover Binary Search Tree

提交网址: https://leetcode.com/problems/recover-binary-search-tree/

Total Accepted: 52083 Total Submissions: 195713 Difficulty: Hard

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

分析:

Morris二叉树遍历算法[非递归、不用栈、空间复杂度为常数]中序遍历(要求得到上升序)情形A:如果2个邻近的节点交换过,那么就只有1个逆序对。情形B:如果2个邻近的节点没有交换过,则有2个逆序对。无论情形A或情形B,交换Inversion Pair(s)的最大值和最小值。

AC代码:

class Solution {
public:
void recoverTree(TreeNode *root) {
    TreeNode *cur, *pre, *node1, *node2;  // node1, node2: Record 2 near nodes
    TreeNode *first, *second;  // Record 2 swapping nodes
    node1 = node2 = first = NULL;
    cur = root;
    while(cur) {
        if(cur->left == NULL) {
            if(node1 == NULL) node1 = cur;
            else if(node2 == NULL) node2 = cur;
            else { node1 = node2; node2 = cur;}
            cur = cur->right;
        } else {
            pre = cur->left;
            while(pre->right && pre->right != cur) pre = pre->right;
            if(pre->right == NULL) {
                pre->right = cur;
                cur = cur->left;
                continue;
            } else {
                pre->right = NULL;
                if(node2 == NULL) node2 = cur;
                else {node1 = node2; node2 = cur;}
                cur = cur->right;
            }
        }
        if(node1 && node2 && node1->val > node2->val) {

            if(first == NULL)  first = node1;
            second = node2;
        }
    }
    /* already learn that there exist 2 nodes swapped.*/
    int t = first->val;
    first->val = second->val;
    second->val = t;
}
};

参考链接:

Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间) - AnnieKim http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

相关链接:

Count Inversions in an array | Set 1 (Using Merge Sort) - GeeksforGeeks http://www.geeksforgeeks.org/counting-inversions/

Given an array of pairs, find all symmetric pairs in it - GeeksforGeeks http://www.geeksforgeeks.org/given-an-array-of-pairs-find-all-symmetric-pairs-in-it/

Using Inversion Pair - An elegent O(n) time complexity and O(1) space complexity Algorithm-Leetcode Discuss

https://leetcode.com/discuss/7319/an-elegent-time-complexity-and-space-complexity-algorithm?show=9834#a9834

剑指offer 面试题36—数组中的逆序对 - 小地盘的诺克萨斯 - 博客频道 - CSDN.NET http://blog.csdn.net/wtyvhreal/article/details/45664949

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016年05月07日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 99. Recover Binary Search Tree
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档