493-翻转对

给定一个数组 nums ,如果 且 我们就将称作一个重要翻转对。 你需要返回给定数组中的重要翻转…

给定一个数组 nums ,如果i<jnums[i]>2*nums[j]我们就将(i,j)称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

前置知识:归并排序、逆序数、分治

公司:阿里、百度、字节

思路1:在归并排序的过程中,假设对于数组nums[l...r]而言,我们已经分别求出了子数组nums[l...m]nums[m+1...r]的翻转对数目,并已将两个子数组分别排好序,则nums[l...r]中的翻转对数目,就等于两个子数组的翻转对数目之和,加上左右端点分别位于两个子数组的翻转对数目。

我们可以为两个数组分别维护指针i,j。对于任意给定的i而言,我们不断地向右移动j,直到nums[i]\leq 2*nums[j]。此时,意味着以i为左端点的翻转对数量为j-m-1。随后,我们再将 ii 向右移动一个单位,并用相同的方式计算以i为左端点的翻转对数量。不断重复这样的过程,就能够求出所有左右端点分别位于两个子数组的翻转对数目。

代码如下:

思路2:暴力法

读完这道题你应该就能联想到逆序数才⾏。求解逆序数最简单的做法是使⽤双层循环暴⼒求解。我们仿照求解决逆序数的解法来解这道题(其实唯⼀的区别就是系数从 1 变成了 2),但是复杂度很高。代码如下:

本文来自网络,不代表软粉网立场,转载请注明出处:https://www.rfff.net/p/4586.html

作者: HUI

发表评论

您的电子邮箱地址不会被公开。

返回顶部