剑指offer之面试题51:数组中的逆序对
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了剑指offer之面试题51:数组中的逆序对,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1274字,纯文字阅读大概需要2分钟。
内容图文
![剑指offer之面试题51:数组中的逆序对](/upload/InfoBanner/zyjiaocheng/1004/6167db88fa79449ca6b15a599796b7e0.jpg)
面试题51:数组中的逆序对
题目:在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。例如,在数组{7, 5, 6, 4}中,一共存在5个逆序对,分别是(7, 6)(7,5)(7,4)(6, 4)和(5, 4)。
思路:
代码实现:
package Question51;
import java.util.Arrays;
public class T01 {
static int count;
public static void main(String[] args) {
int[] arr = {7, 5, 6, 4};
System.out.println(solve(arr));
}
public static int solve(int[] arr) {
if(arr == null && arr.length == 0) return count;
int left = 0, right = arr.length-1;
divide(arr, left, right);
return count;
}
public static void divide(int[] arr, int left, int right) {
//说明只有1个元素
if(left == right) return ;
int mid = left + (right - left) / 2;
divide(arr, left, mid);
divide(arr, mid+1, right);
merge(arr, left, mid, mid+1, right);
}
public static void merge(int[] arr, int left1, int right1, int left2, int right2) {
int[] arr1 = Arrays.copyOfRange(arr, left1, right1+1);
int[] arr2 = Arrays.copyOfRange(arr, left2, right2+1);
int p1 = arr1.length - 1, p2 = arr2.length - 1, p3 = right2;
while(p1 >= 0 && p2 >= 0) {
if(arr1[p1] > arr2[p2]) {
count += p2 + 1;
arr[p3--] = arr1[p1--];
} else arr[p3--] = arr[p2--];
}
while(p1 >= 0) arr[p3--] = arr1[p1--];
while(p2 >= 0) arr[p3--] = arr2[p2--];
}
}
内容总结
以上是互联网集市为您收集整理的剑指offer之面试题51:数组中的逆序对全部内容,希望文章能够帮你解决剑指offer之面试题51:数组中的逆序对所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。