逆序对算法(reverse pair)

逆序对(reverse-pair)

思想和归并排序的思想一样，时间复杂度是O(nlgn)。就是在统计逆序对个数的表达式需要注意一下。

具体实现

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

class Solution {

public:

    //逆序对算法

    int reverse_pair(vector<int>& vec, int p, int r) {

        if (p < r) {

            int q = floor((r + p) / 2);

            reverse_pair(vec, p, q); //划分子问题

            reverse_pair(vec, q + 1, r);

            total_result += merge(vec, p, q, r); //合并

        }

    }

    int merge(vector<int>& vec, int p, int q, int r) {

        vector<int> vec1(vec.begin() + p, vec.begin() + q + 1);

        vector<int> vec2(vec.begin() + q + 1, vec.begin() + r + 1);

        vec1.push_back(INT_MAX);

        vec2.push_back(INT_MAX);

        int i = 0;

        int j = 0;

        int result = 0;

        for (int k = p; k <= r; k++) {

            if (vec1[i] < vec2[j]) {

                vec[k] = vec1[i];

                i++;

            } else {

                vec[k] = vec2[j];

                j++;

                result += (q - i + 1 - p);   // 这个表达式非常重要

            }

        }

        return result;

    }

    int get_result() {

        return total_result;

    }

private:

    int total_result;

};

int main() {

    int arr[] = {2, 3, 8, 6, 1};

    vector<int> vec(arr, arr+5);

    Solution* solution = new Solution();

    solution->reverse_pair(vec, 0, 4);

    cout << solution->get_result() << endl;

    return 0;

}

巴特西

逆序对算法(reverse pair)

逆序对(reverse-pair)

思想和归并排序的思想一样，时间复杂度是O(nlgn)。就是在统计逆序对个数的表达式需要注意一下。

具体实现

最新文章

热门文章

巴特西

逆序对算法(reverse pair)

逆序对(reverse-pair)

思想和归并排序的思想一样，时间复杂度是O(nlgn)。 就是在统计逆序对个数的表达式需要注意一下。

具体实现

最新文章

热门文章

思想和归并排序的思想一样，时间复杂度是O(nlgn)。就是在统计逆序对个数的表达式需要注意一下。