[LintCode] Reverse Pairs
文章目录
Problem
For an array A, if i < j, and A[i] > A[j], called (A[i], A[j]) is a reverse pair.
return total of reverse pairs in A.
Example
Given A = [2, 4, 1, 3, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3
Note
暴力解法就是时灵时不灵,submit两次ac一次。
希望看到的大神能够分享优质的解法^_^ linspiration1991@gmail.com
Solution
public class Solution {
public long reversePairs(int[] A) {
long res = 0;
int n = A.length;
for (int i = 0; i < n-1; i++) {
for (int j = i; j < n; j++) {
if (A[i] > A[j]) res += 1;
}
}
return res;
}
}
//谢谢大家!

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论