C++11(clang++ 3.9) 解法, 执行用时: 43ms, 内存消耗: 2016K, 提交时间: 2020-05-29 22:10:00

#include <bits/stdc++.h>
using namespace std;
#define maxn 100001
int n,ans,a[maxn],b[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]),b[i]=a[i];
	sort(b,b+n);
	for(int i=0;i<n;i++){
		if(a[i]!=b[i]) swap(a[i],a[lower_bound(b,b+n,a[i])-b]),ans++,i--;
	}
	printf("%d",ans);
	return 0;
}

Python3 解法, 执行用时: 318ms, 内存消耗: 19044K, 提交时间: 2023-03-12 12:12:07

N = int(input())
l = [int(input()) for i in range(N)]
d = {b:a for a,b in enumerate(l)}
m = sorted(l)
result = 0
for i in range(len(l)-1):
    if l[i] != m[i]:
        j = d[m[i]]
        l[i],l[j] = l[j],l[i]
        d[l[i]],d[l[j]] = d[l[j]],d[l[i]]
        result += 1
print(result)