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

剑指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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券