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.
Example1:
Input: [1,3,2,3,1] Output: 2
Example2:
Input: [2,4,3,5,1] Output: 3
Note:
- The length of the given array will not exceed
50,000
. - All the numbers in the input array are in the range of 32-bit integer.
ref: https://leetcode.com/problems/reverse-pairs/solution/
BIT: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/
关键是需要一个数据结构可以提供实时排序并计数。binary search tree可以满足,但是最坏情况是O(n^2),得用AVL或Red-Black来实现。而BIT(binary indexed tree) 实现更简单
Solution #1 Binary Indexed Tree,遍历以[i] 为pair里第2位的所有pair,在[0, i - 1]内找所有符合 j < i && nums[j] >= 2 * num[i] + 1的个数并返回。根据算法要返回排序后的[j, i]数量,而普通的BIT实现是[0, i]和,所有这里要修改下read和update方法,使BIT存的是suffix sum。
想验证的该算法的话画一个[1, 8]的BIT就可以了
class Solution { public int reversePairs(int[] nums) { int n = nums.length; int[] bit = new int[n + 1]; int[] sorted = Arrays.copyOf(nums, nums.length); Arrays.sort(sorted); int rt = 0; for (int i = 0; i < n; i++) { int index = getIndex(sorted, nums[i] * 2L + 1); rt += read(bit, index); int index2 = getIndex(sorted, nums[i]); update(bit, index2); } return rt; } private int getIndex(int[] sorted, long val) { int l = 0, r = sorted.length - 1; while (l <= r) { int m = (l + r) / 2; if (sorted[m] >= val) { r = m - 1; }else { l = m + 1; } } return l + 1; } private void update(int[] bit, int idx) { while (idx > 0) { bit[idx] += 1; idx -= idx & -idx; } } private int read(int[] bit, int idx) { int sum = 0; while (idx < bit.length) { sum += bit[idx]; idx += idx & -idx; } return sum; } }
Solution #2, 用merge sort的思路。分成2堆,pair里的第一个在第一堆,第二个在第二堆。这样能保证i < j, 然后再过滤 nums[i] > nums[j] * 2
class Solution { public int reversePairs(int[] nums) { return sort(nums, 0, nums.length - 1); } private int sort(int[] nums, int l, int r) { if (l >= r) { return 0; } int m = (l + r) / 2; int rt = sort(nums, l, m) + sort(nums, m + 1, r); int x = l, z = m + 1; while (x <= m && z <= r) { if (nums[x] > nums[z] * 2L) { rt += m - x + 1; z++; }else { x++; } } int i = l, j = m + 1; int[] backup = new int[r - l + 1]; int p = 0; while (i <= m || j <= r) { if (i > m || (j <= r && nums[i] >= nums[j])) { backup[p++] = nums[j++]; }else { backup[p++] = nums[i++]; } } for (int k = l; k <= r; k++) { nums[k] = backup[k - l]; } return rt; } }
No comments:
Post a Comment