配列の逆順序の対の個数を求めます

テーマ説明Description
N個の実数からなる配列があり、一対の要素A[i]とA[j]が逆配列である場合、すなわちiA[j]は逆配列と呼ばれ、その配列中のすべての逆数を計算するアルゴリズムを設計する.要求アルゴリズム複雑度O(nlogn)
Input
複数の行が入力され、1行目の整数Tはテスト用例の個数として表され、後にT個のテスト用例が表示され、各用例は2行を含み、1行目の整数は要素の個数であり、2行目はスペースで区切られた配列値である.
Output
各使用例の逆転個数を出力し、1行は1つの使用例を表す.
Sample Input 1

1
8
8 3 2 9 7 1 5 4

Sample Output 1

17

構想は主に集計並べ替えに小さな修正を行い,蛮力法の時間複雑度を低減し,O(nlogn)に達する.マージ中に右のシーケンスに左のシーケンスよりも小さい値が見つかった場合、左のシーケンスはその値からmidまでの数で、右の数と逆のシーケンス対を構成します(左右のシーケンスは秩序化されているため).

package LeetCode_19_12;

import java.util.Arrays;

public class     191209 {

	int count = 0;

	public void mergesort(int[] arr) {
		sort(arr, 0, arr.length - 1);
	}

	public void sort(int[] arr, int L, int R) {
		if (L == R) {
			return;
		}
		int mid = L + ((R - L) >> 1);
		sort(arr, L, mid);
		sort(arr, mid + 1, R);
		merge(arr, L, mid, R);
	}

	public void merge(int[] arr, int L, int mid, int R) {

		int[] temp = new int[R - L + 1];
		int i = 0;
		int pa1 = L;
		int pa2 = mid + 1;
		while (pa1 <= mid && pa2 <= R) {

			if (arr[pa1] < arr[pa2]) {
				temp[i] = arr[pa1];
				i++;
				pa1++;
			} else {
				temp[i] = arr[pa2];
				i++;
				pa2++;
				count += mid - pa1 + 1;
				//                  ，                            。
				//               。
			}
		}
		//               temp，                      length
		//            temp
		while (pa1 <= mid) {// <=mid mid        
			temp[i++] = arr[pa1++];
		}
		while (pa2 <= R) {
			temp[i++] = arr[pa2++];
		}
		//         
		for (i = 0; i < temp.length; i++) {
			arr[L + i] = temp[i];
		}
	}

	public static void main(String[] args) {

		int a[] = { 5, 4, 2, 1 };
		int b[] = { 8, 3, 2, 9, 7, 1, 5, 4 };
		    191209 p = new     191209();
		p.mergesort(b);
		System.out.println(Arrays.toString(b));
		System.out.println(p.count);
	}

}