题解 | #数组中的逆序对#
数组中的逆序对
http://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
C语言 求数组中的逆序对(暴力法)
解题思路
不妨对一个数组 1 2 3 5 2 6 7 8 1,求逆序对数,显然是对于每一个数字,看前面有多少组数字比他大,类似于冒泡的思想,最笨的算法:从最后一个遍历,计算前面有多少个数字大于该元素,最终计算求和。这样的最差时间复杂度是 n! 太高了
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param data int整型一维数组
* @param dataLen int data数组长度
* @return int整型
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
int InversePairs(int* data, int dataLen ) {
// 假设一串数组 1 2 3 5 2 6 7 8 1,逆序对肯定是比2大的 以及比最后一个1大的,冒泡排序问题
if(data==NULL||dataLen==0||dataLen==1)
return 0;
long int total=0;
for(int i=dataLen-1;i>=0;i--){
int k=i-1;
while(k>=0){
if(data[i]<data[k])
total++;
k--;
}
}
return total%1000000007;
}