Reverse Pairs
给一个数组, 定义revrese pair是(i,j) nums[i] > 2*nums[j]. 问有几对儿, 这个和普通的reverse pairs没啥区别. 只是多个倍数. 经典算法之一, 这个应该用divide and conquer来做. 注意每次divide完了都sort一下.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class Solution { public int reversePairs(int[] nums) { return mergeSort(nums, 0, nums.length-1); } private int mergeSort(int[] nums, int s, int e){ if(s>=e) { return 0; } int mid = s + (e-s)/2; int cnt = mergeSort(nums, s, mid) + mergeSort(nums, mid+1, e); //divide for(int i = s, j = mid+1; i<=mid; i++){ // i while(j<=e && nums[i]/2.0 > nums[j]) { // nums[j]*2 is too big j++; } cnt += j-(mid+1); //conquer } Arrays.sort(nums, s, e+1); return cnt; } } |