求[9,8,7,6,5,4,3,2,1]数组的逆序对的java代码
时间: 2023-10-06 20:12:51 浏览: 31
public class ReversePairs {
public static int reversePairs(int[] nums) {
int n = nums.length;
int[] temp = new int[n];
return mergeSort(nums, 0, n - 1, temp);
}
public static int mergeSort(int[] nums, int left, int right, int[] temp) {
if (left >= right) {
return 0;
}
int mid = (left + right) / 2;
int leftPairs = mergeSort(nums, left, mid, temp);
int rightPairs = mergeSort(nums, mid + 1, right, temp);
int crossPairs = merge(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
public static int merge(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left, j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j++];
} else if (j == right + 1) {
nums[k] = temp[i++];
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i++];
} else {
nums[k] = temp[j++];
count += (mid - i + 1);
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {9, 8, 7, 6, 5, 4, 3, 2, 1};
System.out.println(reversePairs(nums)); // Output: 36
}
}
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)