@zimenglan
2015-01-20T15:19:30.000000Z
字数 2465
阅读 3240
逆序对
剑指offer
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
输入:
每个测试案例包括两行:
第一行包含一个整数n,表示数组中的元素个数。其中1 <= n <= 10^5。
第二行包含n个整数,每个数组均为int类型。
输出:
对应每个测试案例,输出一个整数,表示数组中的逆序对的总数。
样例输入:
4
7 5 6 4
样例输出:
5
思路一
直接的做法是逐个统计,复杂度是N^2,
思路二:
可以利用归并排序的思想,在排序过程中统计逆序对的个数。
时间复杂度依然是 N*Log(N)。 可以从代码中看到,只是比归并排序多了一句代码:cnt += (end-j+1);
注意:
由于最终个数可能超过int,这里用long long
//============================================================================
// Name : 求逆序对.cpp
// Author : coder
// Version :
// Copyright : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
int n, arr[100010], tmp[100010];
//归并排序,过程中 统计逆序数
ll merge(int start, int mid, int end){
ll cnt = 0;
int i = start, j = mid+1, k = start;
while( i<=mid && j<= end){
//从大到小排序
if(arr[i] > arr[j]){
cnt += (end-j+1); //右面剩下的都是逆序
tmp[k++] = arr[i++];
}else{
tmp[k++] = arr[j++];
}
}
while(i<=mid) tmp[k++] = arr[i++];
while(j<=end) tmp[k++] = arr[j++];
for(int i=start; i<=end; i++) arr[i] = tmp[i];
return cnt;
}
ll inversePairs(int start, int end){
ll cnt = 0;
if(start < end){
int mid = (start + end)/2;
cnt += inversePairs(start, mid); //左半部分 逆序对数量
cnt += inversePairs(mid+1, end); //右半部分
cnt += merge(start, mid, end); //合并两部分,并计算数量
}
return cnt;
}
int main() {
//freopen("in.txt", "r", stdin);
while( scanf("%d", &n) != EOF){
for(int i=0; i<n; i++) scanf("%d", &arr[i]);
ll ans = inversePairs(0, n-1);
printf("%lld\n",ans);
}
return 0;
}
//============================================================================
// Name : 求逆序对.cpp
// Author : coder
// Version :
// Copyright : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
int n, arr[100010], tmp[100010];
//归并排序,过程中 统计逆序数
ll merge(int start, int mid, int end){
ll cnt = 0;
int i = start, j = mid+1, k = start;
while( i<=mid && j<= end){
//从大到小排序
if(arr[i] > arr[j]){
cnt += (end-j+1); //右面剩下的都是逆序
tmp[k++] = arr[i++];
}else{
tmp[k++] = arr[j++];
}
}
while(i<=mid) tmp[k++] = arr[i++];
while(j<=end) tmp[k++] = arr[j++];
for(int i=start; i<=end; i++) arr[i] = tmp[i];
return cnt;
}
ll inversePairs(int start, int end){
ll cnt = 0;
if(start < end){
int mid = (start + end)/2;
cnt += inversePairs(start, mid); //左半部分 逆序对数量
cnt += inversePairs(mid+1, end); //右半部分
cnt += merge(start, mid, end); //合并两部分,并计算数量
}
return cnt;
}
int main() {
//freopen("in.txt", "r", stdin);
while( scanf("%d", &n) != EOF){
for(int i=0; i<n; i++) scanf("%d", &arr[i]);
ll ans = inversePairs(0, n-1);
printf("%lld\n",ans);
}
return 0;
}