归并排序模板(非递归、求逆序对)
程序员文章站
2022-05-10 15:12:25
...
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5限制:
0 <= 数组长度 <= 50000
class Solution {
private int ans=0;
private void merge(int[] nums, int low, int mid, int high) {
int[] tmp = new int[high-low+1];
int k=0, i=low, j=mid+1;
while(i <= mid && j <= high) {
if(nums[i] >= nums[j]) {
tmp[k++] = nums[i++];
}
else {
tmp[k++] = nums[j++];
ans += mid - i + 1;
}
}
while(i <= mid) {
tmp[k++] = nums[i++];
}
while(j <= high) {
tmp[k++] = nums[j++];
}
k=0;
i=low;
while(i <= high) {
nums[i++] = tmp[k++];
}
}
private void mergeSort(int[] nums) {
int low, mid, high;
int size = 1, len = nums.length;
while (size < len) {
low = 0;
while (low + size < len) {
mid = low + size - 1;
high = Math.min(mid + size, len - 1);
merge(nums, low, mid, high);
low = high + 1;
}
size *= 2;
}
}
public int reversePairs(int[] nums) {
mergeSort(nums);
return ans;
}
}
非递归归并排序模板
import java.util.Arrays;
class MergeSort {
public static void main(String[] args) {
int[] nums = {9, 8, 7, 6, 5, 4, 3, 2, 1};
new Solution().mergeSort(nums);
System.out.println(Arrays.toString(nums));
}
private void mergeSort(int[] nums) {
int low, mid, high;
int size = 1, len = nums.length;
while (size < len) {
low = 0;
while (low + size < len) {
mid = low + size - 1;
high = Math.min(mid + size, len - 1);
merge(nums, low, mid, high);
low = high + 1;
}
size *= 2;
}
}
private void merge(int[] nums, int low, int mid, int high) {
int[] tmp = new int[high-low+1];
int k=0, i=low, j=mid+1;
while(i <= mid && j <= high) {
if(nums[i] >= nums[j]) {
tmp[k++] = nums[i++];
}
else {
tmp[k++] = nums[j++];
}
}
while(i <= mid) {
tmp[k++] = nums[i++];
}
while(j <= high) {
tmp[k++] = nums[j++];
}
k=0;
i=low;
while(i <= high) {
nums[i++] = tmp[k++];
}
}
}
上一篇: 排序模板+求逆序对(归并的思想)
下一篇: scrapy在pycharm环境下调试