题目描述补充

题目：逆序对

给定一个整数数组 nums，请计算该数组中逆序对的总数。在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。例如，在数组 [7, 5, 6, 4] 中，逆序对有 (7, 5)、(7, 4)、(6, 4)，因此该数组逆序对的总数为 3。

示例代码

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 示例

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 示例

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

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法基础、数据结构、面试技巧等，欢迎访问码小课网站深入学习。