剑指offer之数组中的逆序对
1 问题
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
比如数列{6,202,100,301,38,8,1},有14个序列对;
比如数列{7, 5, 6, 4},有5个序列对{7,5},{7,6},{7,4},{5,4},{6,4};
2 分析
我们先了解下归并排序,前面博客有介绍 剑指offer之归并排序 ,我们分析数列{6,202,100,301,38,8,1},
第一次归并后:{6,202},{100,301},{8,38},{1},这里逆序对1对,就是我们把8插入了38前面,后面只有38一个数据,所以是一度
第二次归并后:{6,100,202,301},{1,8,38},这里逆序对有3对,我们把100插入了数组{6,202}之间,后面只有202一个元素,所以有一对逆序对,然后1插入了数组{8, 38}最前面,这里后面还有2个元素,所以这有2个逆序对。
第三次归并后:{1,6,8,38,100,202,301},这里逆序对有10对,把1出入了数组{6,100,202,301}最前面,后面有4个数据,所以4对,然后把8插入数组{6,100,202,301}的第二个数据,后面还有3个数据,就是3对,然后再把38插入数组{6,100,202,301}里面,后面还有3个数据,也就是还有3对逆序对
规律:我们把右边数组里面的元素插入左边数组元素的时候,插进去的位置后面到左边数组尾巴多有多少个元素,就有多少个逆序对,每插入依次,我们统计一次,依次累加。
3 代码实现
#include <stdio.h>
int lastResult = 0;
void merge(int* source, int* temp, int start, int mid, int end)
{
if (source == NULL || temp == NULL)
{
printf("merge source or temp is NULL\n");
return;
}
int i = start, j = mid + 1, k = start;
int count = 0;
while (i != mid + 1 && j != end + 1)
{
if (source[i] > source[j])
{
temp[k++] = source[j++];
count = mid - i + 1;
lastResult += count;
}
else
temp[k++] = source[i++];
}
while (i != mid + 1)
temp[k++] = source[i++];
while (j != end + 1)
temp[k++] = source[j++];
for(int h = start; h <= end; ++h)
{
source[h] = temp[h];
}
return;
}
int static result = 0;
void mergeSort(int* source, int* temp, int start, int end)
{
if (source == NULL || temp == NULL)
{
printf("mergeSort source or temp is NULL\n");
return;
}
if (start < end)
{
int mid = start + (end - start) / 2;
mergeSort(source, temp, start, mid);
mergeSort(source, temp, mid + 1, end);
merge(source, temp, start, mid, end);
}
}
void printDatas(int* datas, int len)
{
for (int i = 0; i < len; ++i)
{
printf("%d\t", datas[i]);
}
printf("\n");
}
int main(void) {
int source[] = {7, 5, 6, 4};
int temp[4];
int length = sizeof(source) / sizeof(int);
mergeSort(source, temp, 0, length - 1);
printf("lastResult is %d\n", lastResult % 1000000007);
return 0;
}
4 运行结果
lastResult is 5
这里时间复杂度是O(nlogn),如果我们用暴力求解,时间复杂度就是O(n * n) .
赞 (0)