当前位置： 面试刷题>> 逆序对 (经典算法题500道)
### 题目描述补充
**题目：逆序对**
给定一个整数数组 `nums`，请计算该数组中逆序对的总数。在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。例如，在数组 `[7, 5, 6, 4]` 中，逆序对有 `(7, 5)`、`(7, 4)`、`(6, 4)`，因此该数组逆序对的总数为 3。
### 示例代码
#### PHP 示例
```php
function reversePairs($nums) {
$n = count($nums);
if ($n <= 1) {
return 0;
}
return mergeSortAndCount($nums, 0, $n - 1);
}
function mergeSortAndCount(&$nums, $left, $right) {
if ($left >= $right) {
return 0;
}
$mid = $left + floor(($right - $left) / 2);
$leftCount = mergeSortAndCount($nums, $left, $mid);
$rightCount = mergeSortAndCount($nums, $mid + 1, $right);
$mergeCount = mergeAndCount($nums, $left, $mid, $right);
return $leftCount + $rightCount + $mergeCount;
}
function mergeAndCount(&$nums, $left, $mid, $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
$temp = [];
$count = 0;
while ($i <= $mid && $j <= $right) {
if ($nums[$i] <= $nums[$j]) {
$temp[$k++] = $nums[$i++];
} else {
$temp[$k++] = $nums[$j++];
$count += ($mid - $i + 1); // 右侧所有小于当前左侧元素的个数
}
}
while ($i <= $mid) {
$temp[$k++] = $nums[$i++];
}
while ($j <= $right) {
$temp[$k++] = $nums[$j++];
}
for ($p = 0; $p < $k; $p++) {
$nums[$left + $p] = $temp[$p];
}
return $count;
}
// 示例用法
$nums = [7, 5, 6, 4];
echo reversePairs($nums); // 输出 3
```
#### Python 示例
```python
def reversePairs(nums):
def mergeSortAndCount(left, right):
if left >= right:
return 0
mid = (left + right) // 2
left_count = mergeSortAndCount(left, mid)
right_count = mergeSortAndCount(mid + 1, right)
merge_count = mergeAndCount(left, mid, right)
return left_count + right_count + merge_count
def mergeAndCount(left, mid, right):
i, j, k = left, mid + 1, 0
temp = []
count = 0
while i <= mid and j <= right:
if nums[i] <= nums[j]:
temp.append(nums[i])
i += 1
else:
temp.append(nums[j])
count += (mid - i + 1)
j += 1
while i <= mid:
temp.append(nums[i])
i += 1
while j <= right:
temp.append(nums[j])
j += 1
nums[left:right+1] = temp
return count
return mergeSortAndCount(0, len(nums) - 1)
# 示例用法
nums = [7, 5, 6, 4]
print(reversePairs(nums)) # 输出 3
```
#### JavaScript 示例
```javascript
function reversePairs(nums) {
function mergeSortAndCount(left, right) {
if (left >= right) return 0;
const mid = Math.floor((left + right) / 2);
const leftCount = mergeSortAndCount(left, mid);
const rightCount = mergeSortAndCount(mid + 1, right);
const mergeCount = mergeAndCount(left, mid, right);
return leftCount + rightCount + mergeCount;
}
function mergeAndCount(left, mid, right) {
let i = left, j = mid + 1, k = 0, count = 0;
const temp = [];
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
count += (mid - i + 1);
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (let p = 0; p < k; p++) {
nums[left + p] = temp[p];
}
return count;
}
return mergeSortAndCount(0, nums.length - 1);
}
// 示例用法
const nums = [7, 5, 6, 4];
console.log(reversePairs(nums)); // 输出 3
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于算法基础、数据结构、面试技巧等，欢迎访问码小课网站深入学习。