- 困难
- 中等
- 简单
题目描述
给定一个数组nums
,如果i < j
且nums[i] > 2*nums[j]
我们就将(i, j)
称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。来源,leetcode 每日一题 493. 翻转对
示例:
1.
输入: [1,3,2,3,1]
输出: 2
2.
输入: [2,4,3,5,1]
输出: 3
解题思路
- 最直接的想法:暴力搜索时间超限。
分治思想+归并排序
需要解决三个问题:
- 统计每两个子数组中的翻转对个数
- 统计跨越两个子数组中的翻转对个数
-
代码
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); } };