题目:
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例:
- 示例 1：
输入: [1,3,2,3,1]
输出: 2
- 示例 2：
输入: [2,4,3,5,1]
输出: 3
注意:
- 给定数组的长度不会超过 50000。
- 输入数组中的所有数字都在 32 位整数的表示范围内。
抛砖引玉
数组中取两个数(索引:i、j)，如果满足 i>j，nums[i] > 2*nums[j]，最先想到枚举所有组合统计满足条件的组合数量，题目归为困难，可想而知暴力枚举一定会超时的
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
let len = nums.length,
_result = 0
if (len < 2) return _result
// 枚举所有两数组合
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (nums[i] > 2 * nums[j]) _result++
}
}
return _result
}
数组中取两个数(索引:i、j)，如果满足 i>j，nums[i] > 2*nums[j]，那么索引在 i 到 j 之间大于 nums[i]是数一定可以和 nums[j]组成翻转对
nums[i]>2*nums[j]，比 nums[i]大的数，且在 nums[j]左边，就一定和 nums[j]组成翻转对。
在 j 左边且大于比 nums[i]，假设 j 把数组二分，且分割后的数组递增，那么不用这个比较就可以得到已知存在的翻转对个数为：i-j-1
上面假设了分割后的数组递增，而实际上本题没有给出递增的限制，也不能整体排序（这样会破坏索引位置）。
借助上面二分的逻辑，我们可以针对已经统计过的片段进行局部排序。
[left.i…mid…j…right]
- nums[i] > 2 * nums[j] => j - mid - 1
- [left…right]局部排序，下次二分被归入一个片段
先二分到单个元素再统计
- 片段 sort 排序
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
if (nums.length === 0) return 0
function helper(nums, left, right) {
if (left === right) return 0
const mid = Math.floor((left + right) / 2),
n1 = helper(nums, left, mid),
n2 = helper(nums, mid + 1, right)
let _result = n1 + n2
// 两个二分片段中，第一个片段与后一个片段中个选择一个元素组成的翻转对
let i = left,
j = mid + 1
while (i <= mid) {
while (nums[i] > 2 * nums[j] && j <= right) j++
_result += j - mid - 1
i++
}
// 二分数组合并，且排序
let temp = nums.slice(left, , right+1).sort((a, b) => a - b)
for (let k = 0; k < temp.length; k++) {
nums[left + k] = temp[k]
}
return _result
}
return helper(nums, 0, nums.length - 1)
}
- 片段归并排序
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
if (nums.length === 0) return 0
function helper(nums, left, right) {
if (left === right) return 0
const mid = Math.floor((left + right) / 2),
n1 = helper(nums, left, mid),
n2 = helper(nums, mid + 1, right)
let _result = n1 + n2
// 两个二分片段中，第一个片段与后一个片段中个选择一个元素组成的翻转对
let i = left,
j = mid + 1
while (i <= mid) {
while (nums[i] > 2 * nums[j] && j <= right) j++
_result += j - mid - 1
i++
}
// 二分数组合并，且排序
let temp = Array(right - left + 1),
p1 = left,
p2 = mid + 1,
index = 0
while (p1 <= mid || p2 <= right) {
if (p1 > mid) {
temp[index++] = nums[p2++]
} else if (p2 > right) {
temp[index++] = nums[p1++]
} else {
if (nums[p1] < nums[p2]) {
temp[index++] = nums[p1++]
} else {
temp[index++] = nums[p2++]
}
}
}
for (let k = 0; k < temp.length; k++) {
nums[left + k] = temp[k]
}
return _result
}
return helper(nums, 0, nums.length - 1)
}
博客: 前端小书童
每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目
欢迎关注留言