目录

题目描述

解题思路

【C++】

【Java】

---

https://leetcode.com/problems/reverse-pairs/description/https://leetcode.com/problems/reverse-pairs/description/

题目描述

Given an integer array nums, return the number of reverse pairs in the array.

A reverse pair is a pair (i, j) where:

• 0 <= i < j < nums.length and
• nums[i] > 2 * nums[j].

Example 1:

Input: nums = [1,3,2,3,1]
Output: 2
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1

Example 2:

Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 5, nums[4] = 1, 5 > 2 * 1

Constraints:

• 1 <= nums.length <= 5 * 104
• -231 <= nums[i] <= 231 - 1

解题思路

【C++】

class Solution {
private:vector<int> indexes;vector<int> tmpIdxes;int ret = 0;void merge(vector<int>& nums, int start, int mid, int end) {int p1 = start, p2 = mid + 1, cur = start;while (p1 <= mid && p2 <= end) {while (p2 <= end && (long long) nums[indexes[p1]] <= (long long) nums[indexes[p2]] * 2) {p2++;}ret += end - p2 + 1;p1++;}p1 = start, p2 = mid + 1;while (p1 <= mid && p2 <= end) {tmpIdxes[cur++] = nums[indexes[p1]] > nums[indexes[p2]] ? indexes[p1++] : indexes[p2++];}while (p1 <= mid) {tmpIdxes[cur++] = indexes[p1++];}while (p2 <= end) {tmpIdxes[cur++] = indexes[p2++];}for (int i = start; i <= end; i++) {indexes[i] = tmpIdxes[i];}}void mergeSort(vector<int>& nums, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}}
public:int reversePairs(vector<int>& nums) {if (nums.size() < 2) {return 0;}indexes.resize(nums.size());tmpIdxes.resize(nums.size());for (int i = 0; i < nums.size(); i++) {indexes[i] = i;}ret = 0;mergeSort(nums, 0, nums.size() - 1);return ret;}
};

【Java】

class Solution {private int[] index;private int[] tmpIndex;private int ans;private void merge(int[] nums, int start, int mid, int end) {int p1 = start, p2 = mid + 1, cur = start;while (p1 <= mid && p2 <= end) {while (p2 <= end && nums[index[p1]] <= (long) nums[index[p2]] * 2) {p2++;}ans += end - p2 + 1;p1++;}p1 = start; p2 = mid + 1;while (p1 <= mid && p2 <= end) {if (nums[index[p1]] > nums[index[p2]]) {tmpIndex[cur++] = index[p1++];}else {tmpIndex[cur++] = index[p2++];}}while (p1 <= mid) {tmpIndex[cur++] = index[p1++];}while (p2 <= end) {tmpIndex[cur++] = index[p2++];}for (int i = start; i <= end; i++) {index[i] = tmpIndex[i];}}private void mergeSort(int[] nums, int start, int end) {if (start < end) {int mid = start + (end - start) / 2;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}}public int reversePairs(int[] nums) {index = new int[nums.length];tmpIndex = new int[nums.length];ans = 0;for (int i = 0; i < nums.length; i++) {index[i] = i;}mergeSort(nums, 0, nums.length - 1);return ans;}
}