计算数组中逆序对的同时优化其时间复杂度
发布时间
阅读量：
阅读量
数组中的逆序对
题目描述
给定一组数，在任意两个元素中若前一个数字大于后一个数字，则这两个数字构成一个inversion pair。请设计一种高效的计算方法来统计给定数组中所有inversion pairs的数量。
给定一个整数数组A及其大小n，请计算数组A中的逆序对数量。其中n不超过5000。
暴力破解
遍历每一个数，比较这个数和它后面的，出现逆序情况计数器就 + 1。
import java.util.*;
public class Main {
public int count(int[] A,int n) {
int cnt = 0;
int len = A.length();
for (int i = 0; i < len; ++i) {
for (int j = i + 1; j < len; ++j) {
if (arr[i] > arr[j]) {
cnt++;
}全部评论 (0)
还没有任何评论哟~