2026-04-19：固定长度子数组中的最小逆序对数量。用go说话，给你一个整数数组 nums（长度为 n）和一个整数 k。所谓“逆序对”，指的是在数组中下标满足 i nums[j] 的轻易一双位置 (i， j)。
对某个联络片断（即子数组）而言，统计它里面通盘满足上述条目的逆序对数量，这个数量即是该子数组的“逆序对数量”。
面前推敲 nums 中通盘长度正巧为 k 的连沉稳数组，要求找出其中逆序对数量的最小值并复返。
1
1
1
输入：nums = [5，3，2，1]， k = 4。
输出：6。
评释：
只消一个长度为 k = 4 的子数组：[5， 3， 2， 1]。
在该子数组中，逆序对为：(0， 1)， (0， 2)， (0， 3)， (1， 2)， (1， 3)， 和 (2， 3)。
逆序对总额为 6，因此最小逆序对数量是 6。
题目来独力扣3768。
大体要害如下：
一、中枢前置常识铺垫
1. 逆序对：子数组内满足 inums[j] 的数对，咱们要统计每个长度为k的连沉稳数组的逆序对总额，找最小值。
2. 滑动窗口：数组中通盘长度为k的连沉稳数组，实质是一个固定大小为k的窗口从左向右滑动，每次挪动一位。
3. 树状数组：高效完成单点更新和前缀和查询的数据结构，用来快速统计逆序对（幸免暴力摆列超时）。
4. 龙套化：因为数组元素值最大可达1e9，无法径直用树状数组存储，是以把原数组的值映射为联络的小整数（1，2，3...）。
二、分要害详备实施过程
要害1：龙套化科罚（压缩数值规模）
原数组：[5， 3， 2， 1]
1. 克隆原数组并列序、去重，得到排序去重数组：[1，2，3，5]
2. 把原数组的每个值，替换为它在排序数组中的位置+1（树状数组下标从1入手）：
• 5 → 4
• 3 → 3
• 2 → 2
• 1 → 1
3. 龙套化后的数组：[4， 3， 2， 1]
作用：把超大数值变成1~4的联络整数，适配树状数组。
要害2：启动化中枢变量
1. 启动化树状数组：长度为 龙套化后最大值+1 = 5，启动值全0。
2. 逆序对计数器 inv = 0：记载刻下窗口的逆序对总额。
3. 谜底变量 ans = 最大值：存储通盘窗口的最小逆序对。
4. 固定窗口大小：k=4。
要害3：滑动窗口遍历数组（一一元素科罚）
咱们遍历龙套化后的数组 [4，3，2，1]，每一步分为：元素入窗口 → 臆度逆序对 → 窗口成型则更新谜底 → 元素出窗口。
第1次遍历（科罚第一个元素：4）
1. 元素入窗口：把数字4加入树状数组，树状数组标志4的位置计数+1。
2. 累加逆序对：刻下窗口内比4大的数字个数为0，逆序对总额 inv = 0。
3. 窗口判断：刻下窗口长度=1
第2次遍历（科罚第二个元素：3）
1. 元素入窗口：把数字3加入树状数组，树状数组标志3的位置计数+1。
2. 累加逆序对：刻下窗口内比3大的数字只消4，逆序对总额 inv = 1。
3. 窗口判断：刻下窗口长度=2
第3次遍历（科罚第三个元素：2）
1. 元素入窗口：把数字2加入树状数组，树状数组标志2的位置计数+1。
2. 累加逆序对：刻下窗口内比2大的数字有4、3，逆序对总额 inv = 1+2=3。
3. 窗口判断：刻下窗口长度=3
第4次遍历（科罚第四个元素：1）
1. 元素入窗口：把数字1加入树状数组，树状数组标志1的位置计数+1。
2. 累加逆序对：刻下窗口内比1大的数字有4、3、2，滚球app下载逆序对总额 inv = 3+3=6。
3. 窗口判断：窗口长度=4，刚好酿成第一个灵验窗口。
4. 更新最小谜底：刻下逆序对总额6是最小值，ans=6。
5. 元素出窗口：窗口左侧第一个元素4移出树状数组，树状数组标志4的位置计数-1。
6. 修正逆序对：减去移出元素4带来的逆序对数量，逆序对总额更新。
要害4：遍历达成，输出扫尾
通盘数组遍历完成，唯独的灵验窗口逆序对总额为6，最终复返6。
三、要害逻辑补充确认
1. 元素入窗口时：用树状数组快速查询刻下窗口中比新元素大的数字个数，径直累加到逆序对总额。
2. 窗口成型后：用刻下逆序对总额更新最小值。
3. 元素出窗口时：用树状数组快速查询比移出元素小的数字个数，从逆序对总额中减去（因为这个元素离开了窗口，它孝顺的逆序对也要删掉）。
4. 提前远隔：要是逆序对总额变为0（表面最小值），径直达成臆度，优化后果。
四、时分复杂度分析
1. 龙套化：排序+去重+映射，时分复杂度为 O(n log n)。
2. 滑动窗口遍历：遍历n个元素，每个元素实施2次树状数组操作（更新+查询），树状数组单次操作复杂度为 O(log m)（m是龙套化后的数值规模，m≤n）。
总遍历复杂度：O(n log n)。
总的时分复杂度：O(n log n)
（这是科罚n≤1e5数据的最优复杂度，能完好通过题目舍弃）
五、迥殊空间复杂度分析
迥殊空间指除输入数组外，代码主动引诱的空间：
1. 龙套化用的排序数组：O(n)。
2. 树状数组：O(n)。
3. 其他临时变量：O(1)。
总的迥殊空间复杂度：O(n)
转头
1. 实施进程：龙套化压缩数值 → 滑动窗口遍历元素 → 树状数组高效统计逆序对 → 调度最小逆序对数量；
2. 时分复杂度：O(n log n)，适配1e5限制数据；
3. 迥殊空间复杂度：O(n)。
Go完整代码如下：
package main
import (
"fmt"
"math"
"slices"
"sort"
)
type fenwick []int
func (t fenwick) update(i， val int) {
for ; i
t[i] += val
}
}
func (t fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res += t[i]
}
return
}
func minInversionCount(nums []int， k int)int64 {
// 龙套化
sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)
for i， x := range nums {
nums[i] = sort.SearchInts(sorted， x) + 1// 树状数组下标从 1 入手
}
t := make(fenwick， len(sorted)+1)
inv := 0
ans := math.MaxInt
for i， in := range nums {
// 1. 入
t.update(in， 1)
inv += min(i+1， k) - t.pre(in) // 窗口大小 - (x 的元素个数)
left := i + 1 - k
if left
continue
}
// 2. 更新谜底
ans = min(ans， inv)
if ans == 0 { // 依然最小了，无需再臆度
break
}
// 3. 出
out := nums[left]
inv -= t.pre(out - 1) //
t.update(out， -1)
}
returnint64(ans)
}
func main {
nums := []int{5， 3， 2， 1}
k := 4
result := minInversionCount(nums， k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
class Fenwick:
def __init__(self， n: int):
self.n = n
self.bit = [0] * (n + 1)
def update(self， i: int， val: int) -> None:
"""将位置i增多val（i从1入手）"""
while i
self.bit[i] += val
i += i & -i
def pre(self， i: int) -> int:
"""前缀和：1到i的和"""
res = 0
while i > 0:
res += self.bit[i]
i &= i - 1
return res
def min_inversion_count(nums: List[int]， k: int) -> int:
"""
臆度通盘长度为k的子数组中逆序对的最小值
"""
# 龙套化
sorted_nums = sorted(set(nums))
# 映射到1，2，3，...（树状数组下标从1入手）
num_to_idx = {val: idx + 1for idx， val in enumerate(sorted_nums)}
nums = [num_to_idx[x] for x in nums]
# 树状数组
bit = Fenwick(len(sorted_nums))
inv = 0 # 刻下窗口的逆序对数
ans = float('inf')
for i， num in enumerate(nums):
# 1. 入：将刻下元素加入窗口
bit.update(num， 1)
# 窗口大小 = min(i+1， k)
window_size = min(i + 1， k)
# 大于num的元素个数 = 窗口大小 - 小于等于num的元素个数
inv += window_size - bit.pre(num)
left = i + 1 - k
if left
# 尚未酿成第一个窗口
continue
# 2. 更新谜底
ans = min(ans， inv)
if ans == 0:
# 依然是最小值，无需连续臆度
break
# 3. 出：移除窗口最左边的元素
out_num = nums[left]
# 小于out_num的元素个数（这些元素与out_num组成逆序对）
inv -= bit.pre(out_num - 1)
bit.update(out_num， -1)
returnint(ans)
def main:
nums = [5， 3， 2， 1]
k = 4
result = min_inversion_count(nums， k)
print(result)
if __name__ == "__main__":
main
C++完整代码如下：
#include
#include
#include
#include
using namespace std;
class Fenwick {
private:
vector bit;
public:
Fenwick(int n) : bit(n + 1， 0) {}
void update(int i， int val) {
for (; i
bit[i] += val;
}
}
int pre(int i) {
int res = 0;
for (; i > 0; i &= i - 1) {
res += bit[i];
}
return res;
}
};
long long minInversionCount(vector& nums， int k) {
// 龙套化
vector sorted = nums;
sort(sorted.begin， sorted.end);
sorted.erase(unique(sorted.begin， sorted.end)， sorted.end);
for (int i = 0; i
nums[i] = lower_bound(sorted.begin， sorted.end， nums[i]) - sorted.begin + 1; // 树状数组下标从1入手
}
Fenwick bit(sorted.size);
int inv = 0;
int ans = INT_MAX;
for (int i = 0; i
int in = nums[i];
// 1. 入
bit.update(in， 1);
inv += min(i + 1， k) - bit.pre(in); // 窗口大小 - (x的元素个数)
int left = i + 1 - k;
if (left
continue;
}
// 2. 更新谜底
ans = min(ans， inv);
if (ans == 0) { // 依然最小了，无需再臆度
break;
}
// 3. 出
int out = nums[left];
inv -= bit.pre(out - 1); //
bit.update(out， -1);
}
return (long long)ans;
}
int main {
vector nums = {5， 3， 2， 1};
int k = 4;
long long result = minInversionCount(nums， k);
cout
return0;
}
咱们敬佩东说念主工智能为等闲东说念主提供了一种“增强用具”，并神敢于共享全主见的AI常识。在这里，您不错找到最新的AI科普著作、用具评测、进步后果的秘密以及行业瞻念察。
接待关怀“福大大架构师逐日一题”滚球app官网，发音讯可取得口试辛劳，让AI助力您的明天发展。
米兰体育(MilanSports)官网
备案号: