网站建设动画教程,南坪做网站,展览会网站建设,wordpress meta query1 问题
在数组中的两个数字#xff0c;如果前面一个数字大于后面的数字#xff0c;则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
比如数列{6#xff0c;202#xff0c;100#xf…1 问题
在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
比如数列{62021003013881}有14个序列对
比如数列{7, 5, 6, 4}有5个序列对{7,5}{7,6}{7,4}{5,4}{6,4} 2 分析
我们先了解下归并排序前面博客有介绍 剑指offer之归并排序 我们分析数列{62021003013881}
第一次归并后{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.hint 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;}elsetemp[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
这里时间复杂度是Onlogn,如果我们用暴力求解时间复杂度就是O(n * n) .
