剑指 Offer——数组中的逆序对

1. 题目

2. 解答

借助于归并排序的分治思想，在每次合并的时候统计逆序对。因为要合并的两个数组都是有序的，如果左半部分数组当前值大于右半部分数组当前值，那么左半部分数组当前值右边的数就都大于右半部分数组当前值，这些数据对也就构成了逆序数对。

比如上图中 [3, 8, 9, 11] 和 [1, 2, 5, 6] 合并的时候，发现 3>1，那么 (3, 1)、(8, 1)、(9, 1) 和 (11, 1) 就构成了 4 个逆序数对，逆序对数加 4。

下面的代码中定义了一个 result 来记录逆序对数，由于逆序对的总数可能很大，所以每次增加其值后要进行一个除余操作。

class Solution {

public:

    int result = 0;

    int InversePairs(vector<int> data) {

        int len = data.size();

        vector<int> temp(len);

        MergeSort(data, temp, 0, len-1);

        return result;

    }

    void MergeSort(vector<int>& data, vector<int>& temp, int begin, int end)

    {

        if (begin < end)

        {

            int mid = (end - begin) / 2 + begin;

            MergeSort(data, temp, begin, mid);

            MergeSort(data, temp, mid+1, end);

            MergeArray(data, temp, begin, mid, end);

        }

    }

    void MergeArray(vector<int>& data, vector<int>& temp, int begin, int mid, int end)

    {

        int i = begin;

        int j = mid + 1;

        int k = 0;

        while (i <= mid && j <= end)

        {

            if (data[i] < data[j])

            {

                temp[k++] = data[i++];

            }

            // 若左半部分当前元素大于右半部分当前元素

            // 则左半部分当前元素后面的每个值都大于它

            else

            {

                result += (mid - i + 1);

                result %=  1000000007;

                temp[k++] = data[j++];

            }

        }

        while (i <= mid)

        {

            temp[k++] = data[i++];

        }

        while (j <= end)

        {

            temp[k++] = data[j++];

        }

        for (i = 0; i < k; i++)

        {

            data[begin+i] = temp[i];

        }

    }

};

获取更多精彩，请关注「seniusen」!

巴特西

剑指 Offer——数组中的逆序对

1. 题目

2. 解答

最新文章

热门文章