Description
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
Example
Example1:
1 2
| Input: [1,3,2,3,1] Output: 2
|
Example2:
1 2
| Input: [2,4,3,5,1] Output: 3
|
Solution
- Time Complexity:
- Space Complexity:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| class Solution { public int reversePairs(int[] nums) { if (nums == null || nums.length == 0) return 0; return mergeSort(nums, 0, nums.length - 1); } private int mergeSort(int[] nums, int left, int right){ if (left >= right) return 0; int mid = left + (right - left) / 2; int res = 0; res += mergeSort(nums, left, mid); res += mergeSort(nums, mid + 1, right); res += merge(nums, left, mid, right); return res; } private int merge(int[] nums, int left, int mid, int right){ int count = 0; int p = left, q = mid + 1; while (p <= mid && q <= right){ if ((long) nums[p] > 2 * (long) nums[q]){ count += mid - p + 1; q++; } else{ p++; } } int[] temp = new int[right - left + 1]; p = left; q = mid + 1; int index = 0; while (p <= mid && q <= right){ if (nums[p] > nums[q]){ temp[index++] = nums[q++]; } else{ temp[index++] = nums[p++]; } } while (p <= mid){ temp[index++] = nums[p++]; } while (q <= right){ temp[index++] = nums[q++]; } System.arraycopy(temp, 0, nums, left, right - left + 1); return count; } }
|