python3 解法, 执行用时: 1844 ms, 内存消耗: 22.6 MB, 提交时间: 2023-10-08 23:40:04

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        tb, res = [], 0
        for n in reversed(nums) :
            res += bisect.bisect_left(tb, n)
            n2 = 2*n
            idx = bisect.bisect_left(tb, n2)
            tb.insert(idx, n2)
        return res

python3 解法, 执行用时: 1500 ms, 内存消耗: 21.8 MB, 提交时间: 2023-10-08 23:39:41

class Solution:
    def find_reversed_pairs(self, nums, left, right):
        res,mid = 0,(left+right)//2
        
        j = mid+1
        for i in range(left,mid+1):
            while j <= right and nums[i] > 2*nums[j]:
                res += mid-i+1
                j += 1
        return res      
        
    def merge_sort(self, nums, nums_sorted, l, r):
        if l >= r: return 0
        mid = (l+r) // 2
        res = self.merge_sort(nums,nums_sorted,l,mid) +\
              self.merge_sort(nums,nums_sorted,mid+1,r) +\
              self.find_reversed_pairs(nums,l,r)
        
        i,j,k = l,mid+1,l
        while i <= mid and j <= r:
            if nums[i] <= nums[j]:
                nums_sorted[k] = nums[i]
                i += 1
            else:
                nums_sorted[k] = nums[j]
                j += 1
            k += 1
                
        while i <= mid:
            nums_sorted[k] = nums[i]
            i += 1
            k += 1
        while j <= r:
            nums_sorted[k] = nums[j]
            j += 1
            k += 1
        
        for k in range(l,r+1): nums[k] = nums_sorted[k]
        
        return res
        
    
    def reversePairs(self, nums: List[int]) -> int:
        if not nums: return 0
        nums_sorted = [0] * len(nums)
        return self.merge_sort(nums,nums_sorted,0,len(nums)-1)

golang 解法, 执行用时: 108 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-08 23:38:57

func reversePairs(nums []int) int {
    n := len(nums)
    if n <= 1 {
        return 0
    }

    n1 := append([]int(nil), nums[:n/2]...)
    n2 := append([]int(nil), nums[n/2:]...)
    cnt := reversePairs(n1) + reversePairs(n2) // 递归完毕后，n1 和 n2 均为有序

    // 统计重要翻转对 (i,j) 的数量
    // 由于 n1 和 n2 均为有序，可以用两个指针同时遍历
    j := 0
    for _, v := range n1 {
        for j < len(n2) && v > 2*n2[j] {
            j++
        }
        cnt += j
    }

    // n1 和 n2 归并填入 nums
    p1, p2 := 0, 0
    for i := range nums {
        if p1 < len(n1) && (p2 == len(n2) || n1[p1] <= n2[p2]) {
            nums[i] = n1[p1]
            p1++
        } else {
            nums[i] = n2[p2]
            p2++
        }
    }
    return cnt
}

golang 解法, 执行用时: 168 ms, 内存消耗: 12.5 MB, 提交时间: 2023-10-08 23:38:40

type fenwick struct {
    tree []int
}

func newFenwickTree(n int) fenwick {
    return fenwick{make([]int, n+1)}
}

func (f fenwick) add(i int) {
    for ; i < len(f.tree); i += i & -i {
        f.tree[i]++
    }
}

func (f fenwick) sum(i int) (res int) {
    for ; i > 0; i &= i - 1 {
        res += f.tree[i]
    }
    return
}

func reversePairs(nums []int) (cnt int) {
    n := len(nums)
    if n <= 1 {
        return
    }

    // 离散化所有下面统计时会出现的元素
    allNums := make([]int, 0, 2*n)
    for _, v := range nums {
        allNums = append(allNums, v, 2*v)
    }
    sort.Ints(allNums)
    k := 1
    kth := map[int]int{allNums[0]: k}
    for i := 1; i < 2*n; i++ {
        if allNums[i] != allNums[i-1] {
            k++
            kth[allNums[i]] = k
        }
    }

    t := newFenwickTree(k)
    for i, v := range nums {
        // 统计之前插入了多少个比 2*v 大的数
        cnt += i - t.sum(kth[2*v])
        t.add(kth[v])
    }
    return
}

javascript 解法, 执行用时: 512 ms, 内存消耗: 75.5 MB, 提交时间: 2023-10-08 23:38:25

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    const allNumbers = Array.from(
        new Set([...nums, ...nums.map(x => 2 * x)]
        .sort((x, y) => x - y))
    );
    // 利用哈希表进行优化
    const values = new Map();
    let idx = 0;
    allNumbers.forEach(x => values.set(x, ++idx));

    let ret = 0;
    const bit = new BIT(values.size);
    for (let i = 0; i < nums.length; i++) {
        let left = values.get(nums[i] * 2), right = values.size;
        ret += bit.query(right) - bit.query(left);
        bit.update(values.get(nums[i]), 1);
    }
    return ret;
};

let BIT = class {
    constructor(n) {
        this.n = n;
        this.tree = new Array(n + 1).fill(0);
    }

    lowbit(x) {
        return x & (-x);
    }

    update(x, d) {
        while (x <= this.n) {
            this.tree[x] += d;
            x += this.lowbit(x);
        }
    }

    query(x) {
        let ans = 0;
        while (x > 0) {
            ans += this.tree[x];
            x -= this.lowbit(x);
        }
        return ans;
    }
}

javascript 解法, 执行用时: 152 ms, 内存消耗: 52.2 MB, 提交时间: 2023-10-08 23:38:09

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if (nums.length === 0) {
        return 0;
    }
    return reversePairsRecursive(nums, 0, nums.length - 1);
};

const reversePairsRecursive = (nums, left, right) => {
    if (left === right) {
        return 0;
    } else {
        const mid = Math.floor((left + right) / 2);
        const n1 = reversePairsRecursive(nums, left, mid);
        const n2 = reversePairsRecursive(nums, mid + 1, right);
        let ret = n1 + n2;

        let i = left;
        let j = mid + 1;
        while (i <= mid) {
            while (j <= right && nums[i] > 2 * nums[j]) {
                j++;
            }
            ret += j - mid - 1;
            i++;
        }

        const sorted = new Array(right - left + 1);
        let p1 = left, p2 = mid + 1;
        let p = 0;
        while (p1 <= mid || p2 <= right) {
            if (p1 > mid) {
                sorted[p++] = nums[p2++];
            } else if (p2 > right) {
                sorted[p++] = nums[p1++];
            } else {
                if (nums[p1] < nums[p2]) {
                    sorted[p++] = nums[p1++];
                } else {
                    sorted[p++] = nums[p2++];
                }
            }
        }
        for (let k = 0; k < sorted.length; k++) {
            nums[left + k] = sorted[k];
        }
        return ret;
    }
}

java 解法, 执行用时: 48 ms, 内存消耗: 52.4 MB, 提交时间: 2023-10-08 23:37:55

class Solution {
    public int reversePairs(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        return reversePairsRecursive(nums, 0, nums.length - 1);
    }

    public int reversePairsRecursive(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
                    j++;
                }
                ret += j - mid - 1;
                i++;
            }

            // 随后合并两个排序数组
            int[] sorted = new int[right - left + 1];
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int k = 0; k < sorted.length; k++) {
                nums[left + k] = sorted[k];
            }
            return ret;
        }
    }
}

java 解法, 执行用时: 160 ms, 内存消耗: 63.8 MB, 提交时间: 2023-10-08 23:37:44

class Solution {
    public int reversePairs(int[] nums) {
        Set<Long> allNumbers = new TreeSet<Long>();
        for (int x : nums) {
            allNumbers.add((long) x);
            allNumbers.add((long) x * 2);
        }
        // 利用哈希表进行离散化
        Map<Long, Integer> values = new HashMap<Long, Integer>();
        int idx = 0;
        for (long x : allNumbers) {
            values.put(x, idx);
            idx++;
        }

        int ret = 0;
        BIT bit = new BIT(values.size());
        for (int i = 0; i < nums.length; i++) {
            int left = values.get((long) nums[i] * 2), right = values.size() - 1;
            ret += bit.query(right + 1) - bit.query(left + 1);
            bit.update(values.get((long) nums[i]) + 1, 1);
        }
        return ret;
    }
}

class BIT {
    int[] tree;
    int n;

    public BIT(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }

    public static int lowbit(int x) {
        return x & (-x);
    }

    public void update(int x, int d) {
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }

    public int query(int x) {
        int ans = 0;
        while (x != 0) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
}

cpp 解法, 执行用时: 320 ms, 内存消耗: 88.6 MB, 提交时间: 2023-10-08 23:37:33

class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int _n) : n(_n), tree(_n + 1) {}

    static constexpr int lowbit(int x) {
        return x & (-x);
    }

    void update(int x, int d) {
        while (x <= n) {
            tree[x] += d;
            x += lowbit(x);
        }
    }

    int query(int x) const {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        set<long long> allNumbers;
        for (int x : nums) {
            allNumbers.insert(x);
            allNumbers.insert((long long)x * 2);
        }
        // 利用哈希表进行离散化
        unordered_map<long long, int> values;
        int idx = 0;
        for (long long x : allNumbers) {
            values[x] = ++idx;
        }

        int ret = 0;
        BIT bit(values.size());
        for (int i = 0; i < nums.size(); i++) {
            int left = values[(long long)nums[i] * 2], right = values.size();
            ret += bit.query(right) - bit.query(left);
            bit.update(values[nums[i]], 1);
        }
        return ret;
    }
};

cpp 解法, 执行用时: 404 ms, 内存消耗: 109 MB, 提交时间: 2023-10-08 23:36:52

class Solution {
public:
    int reversePairsRecursive(vector<int>& nums, int left, int right) {
        if (left == right) {
            return 0;
        } else {
            int mid = (left + right) / 2;
            int n1 = reversePairsRecursive(nums, left, mid);
            int n2 = reversePairsRecursive(nums, mid + 1, right);
            int ret = n1 + n2;

            // 首先统计下标对的数量
            int i = left;
            int j = mid + 1;
            while (i <= mid) {
                while (j <= right && (long long)nums[i] > 2 * (long long)nums[j]) j++;
                ret += (j - mid - 1);
                i++;
            }

            // 随后合并两个排序数组
            vector<int> sorted(right - left + 1);
            int p1 = left, p2 = mid + 1;
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                if (p1 > mid) {
                    sorted[p++] = nums[p2++];
                } else if (p2 > right) {
                    sorted[p++] = nums[p1++];
                } else {
                    if (nums[p1] < nums[p2]) {
                        sorted[p++] = nums[p1++];
                    } else {
                        sorted[p++] = nums[p2++];
                    }
                }
            }
            for (int i = 0; i < sorted.size(); i++) {
                nums[left + i] = sorted[i];
            }
            return ret;
        }
    }

    int reversePairs(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        return reversePairsRecursive(nums, 0, nums.size() - 1);
    }
};