每日算法之数组中的逆序对
JZ51 数组中的逆序对题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
方法1：暴力
思路
算法实现
两个for循环，如果前面的数大于后面的计数加1即可
问题
当输入数过大时，需要的时间会很长，所以此方法不行
代码
package mid.JZ51数组中的逆序对;
import java.util.ArrayList;
public class Solution {
public int InversePairs1(int[] array) {
int k = 1000000007;
if (array.length <= 1) return 0;
int res = 0;
for (int i = 1; i < array.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (array < array)
res++;
}
}
return res % k;
}
}方法2 归并排序思想
思路
[*]先分：分呢，就是将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止！
[*]后并：并呢，就是从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组！
[*]归并统计法，关键点在于合并环节，在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。
代码
package mid.JZ51数组中的逆序对;import java.util.Arrays;public class Solution { /** * 分治 * * @param array * @return */ public int count = 0; public int InversePairs(int[] array) { divMerge(array, 0, array.length-1); return count; } public void divMerge(int[] array, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; //分左边 divMerge(array, left, mid); //分右边 divMerge(array, mid + 1, right); //合并 int i = left; int j = mid + 1; //临时数组 int[] tmp = new int; int k = 0; while (i
页:
[1]