数组中的逆序对
题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
输入描述：
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
输入：
12345670
输出：
1 7
思路
如数组{7,5,6,4}，逆序对总共有5对，{7,5}，{7,6}，{7,4}，{5,4}，{6,4}；
思路1：暴力解法，顺序扫描整个数组，每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成一个逆序对。假设数组中含有n个数字，由于每个数字都要和O(n)个数字作比较，因此这个算法的时间复杂度是O(n^2)。
思路2：分治思想，采用归并排序的思路来处理，如下图，先分后治：
先把数组分解成两个长度为2的子数组，再把这两个子数组分解成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7>5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}，{4}中也有逆序对（6,4），由于已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行排序，避免在之后的统计过程中重复统计。
逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量
总结一下：
这是一个归并排序的合并过程，主要是考虑合并两个有序序列时，计算逆序对数。
对于两个升序序列，设置两个下标：两个有序序列的末尾。每次比较两个末尾值，如果前末尾大于后末尾值，则有”后序列当前长度“个逆序对；否则不构成逆序对。然后把较大值拷贝到辅助数组的末尾，即最终要将两个有序序列合并到辅助数组并有序。
这样，每次在合并前，先递归地处理左半段、右半段，则左、右半段有序，且左右半段的逆序对数可得到，再计算左右半段合并时逆序对的个数。
代码
public class Solution {
int count =0;
public int InversePairs(int [] array) {
if(array == null || array.length ==0){
return 0;
}
split(array,0,array.length-1);
return count;
}
public void split(int[] array,int start,int end){
if(start < end){
int mid = (start + end)/2;
split(array,start,mid);
split(array,mid+1,end);
heapMax(array,start,mid,mid+1,end);
}
}
public void heapMax(int[] array,int start1,int end1,int start2,int end2){
int i = end1;
int j = end2;
int[] temp = new int[end2-start1+1];
int index = end2-start1;
while(start1 <=i && start2 <= j){
if(array[i] > array[j]){
count =count +j-start2+1;
temp[index--] = array[i--];
count %= 1000000007;
}else{
temp[index--] = array[j--];
}
}
while(start1 <= i){
temp[index--] = array[i--];
}
while(start2 <= j){
temp[index--] = array[j--];
}
int m = start1;
for(int element:temp)
{
array[m++] = element;
}
}
}public class inversePairsCore {
public static void main(String[] args) {
int[] data ={1, 2, 3, 4, 7, 6, 5};
System.out.println(inversePairs(data));
}
public static int inversePairs(int[] data) {
if (data == null || data.length < 1) {
throw new IllegalArgumentException("Array arg should contain at least a value");
}
int[] copy = new int[data.length];
System.arraycopy(data, 0, copy, 0, data.length);
return inversePairsCore(data, copy, 0, data.length - 1);
}
private static int inversePairsCore(int[] data, int[] copy, int start, int end) {
if (start == end) {
copy[start] = data[start];
return 0;
}
int length = (end - start) / 2;
int left = inversePairsCore(copy, data, start, start + length);
int right = inversePairsCore(copy, data, start + length + 1, end);
// 前半段的最后一个数字的下标
int i = start + length;
// 后半段最后一个数字的下标
int j = end;
// 开始拷贝的位置
int indexCopy = end;
// 逆序数
int count = 0;
while (i >= start && j >= start + length + 1) {
if (data[i] > data[j]) {
copy[indexCopy] = data[i];
indexCopy--;
i--;
count += j - (start + length);
// 对应的逆序数
} else {
copy[indexCopy] = data[j];
indexCopy--;
j--;
}
}
for (; i >= start;) {
copy[indexCopy] = data[i];
indexCopy--;
i--;
}
for (; j >= start + length + 1;) {
copy[indexCopy] = data[j];
indexCopy--;
j--;
}
return count + left + right;
}
}
Java中System.arraycopy方法的使用
System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制。
其函数原型是：
public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)
1
src:源数组；
srcPos:源数组要复制的起始位置；
dest:目的数组；
destPos:目的数组放置的起始位置；
length:复制的长度。
注意：src and dest都必须是同类型或者可以进行转换类型的数组．
代码2
static int count = 0;
public static void main(String[] args) {
}
public static int InversePairs(int [] array) {
if(array == null || array.length ==0)
{
return 0;
}
mergeSort(array, 0, array.length -1);
return count;
}
public static void mergeSort(int []array, int start, int end) {
if(start < end) {
int mid = (start + end)/2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, mid+ 1, end);
}
}
public static void merge(int []array,int start1,int end1, int start2, int end2) {
int i = end1;
int j = end2;
int k = end2 - start1 ;
int [] temp = new int[end2- start1 +1];
while(i >= start1 && j >=start2) {
if(array[i] > array[j]) {
//假设此时两个归并的是17 19 22 || 16 18 21
//那么22大于21，所以可以看出对应22
//有三个，22 16 22 18 22 21
temp[k--] = array[i--];
count = count + j - start2 +1;
count %= 1000000007;
}
else
{
temp[k--] = array[j--];
}
}
while(i >= start1)
{
temp[k--] = array[i--];
}
while(j >= start2)
{
temp[k--] = array[j--];
}
int m = start1;
for(int element:temp)
{
array[m++] = element;
}
}
}
LeetCode
给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例:
输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.
(未完待续。。。。。。。)
京公网安备 11010502036488号