-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-327-Count-of-Range-Sum.java
135 lines (110 loc) · 4.96 KB
/
LeetCode-327-Count-of-Range-Sum.java
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class Solution {
// My Solution with Merge Sort. Wrong Answer, cannot handle edge case: [0] 0 0
// public int countRangeSum(int[] nums, int lower, int upper) {
// List<Integer> sum = new ArrayList<>();
// int[] tmp = new int[nums.length];
// mergeSort(nums, lower, upper, 0, nums.length - 1, tmp, sum);
// int count = 0;
// for (int i : sum) {
// System.out.print(i + " ");
// if (i >= lower && i <= upper) {
// count++;
// }
// }
// return count;
// }
// private void mergeSort(int[] nums, int lower, int upper, int lo, int hi, int[] tmp, List<Integer> sum) {
// if (lo >= hi) {
// // Edge case: [0] 0 0
// // if (nums[lo] >= lower && nums[lo] <= upper) sum.add(nums[lo]);
// return;
// }
// int mid = lo + (hi - lo) / 2;
// mergeSort(nums, lower, upper, lo, mid, tmp, sum);
// mergeSort(nums, lower, upper, mid + 1, hi, tmp, sum);
// merge(nums, lower, upper, lo, mid, hi, tmp, sum);
// }
// private void merge(int[] nums, int lower, int upper, int lo, int mid, int hi, int[] tmp, List<Integer> sum) {
// for (int k = lo; k <= hi; k++) {
// tmp[k] = nums[k];
// }
// int i = lo, j = mid + 1;
// int s = 0;
// for (int k = lo; k <= hi; k++) {
// if (j > hi || (i <= mid && tmp[i] <= tmp[j])) {
// nums[k] = tmp[i];
// i++;
// } else {
// nums[k] = tmp[j];
// j++;
// }
// s += nums[k];
// sum.add(s);
// }
// }
// Merge Sort + Prefix Sum
/*
https://leetcode.com/problems/count-of-range-sum/discuss/77990/Share-my-solution
This solution is a combination of Merge Sort and Prefix Sum. It basically does the merge sort in prefix sum array, and count during merge sort.
Must use long[] for prefix sum array, as the sum result may exceeds the boundary.
Edge case: [-2147483647,0,-2147483647,2147483647] -564 3864
Using long[] for prefix sum: sum: [0, -2147483647, -2147483647, -4294967294, -2147483647]
Using int[] for prefix sum: prefixSum: [0, -2147483647, -2147483647, 2, -2147483647]
*/
public int countRangeSum(int[] nums, int lower, int upper) {
long[] prefixSum = new long[nums.length + 1];
prefixSum[0] = 0;
for (int i = 1; i <= nums.length; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
long[] tmp = new long[prefixSum.length];
int[] result = new int[1];
mergeSort(prefixSum, lower, upper, tmp, 0, prefixSum.length - 1, result);
return result[0];
}
private void mergeSort(long[] prefixSum, int lower, int upper, long[] tmp, int lo, int hi, int[] result) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
// System.out.println("lo: " + lo + " mid: " + mid + " hi: " + hi);
mergeSort(prefixSum, lower, upper, tmp, lo, mid, result);
mergeSort(prefixSum, lower, upper, tmp, mid + 1, hi, result);
merge(prefixSum, lower, upper, tmp, lo, mid, hi, result);
}
private void merge(long[] prefixSum, int lower, int upper, long[] tmp, int lo, int mid, int hi, int[] result) {
for (int k = lo; k <= hi; k++) {
tmp[k] = prefixSum[k];
}
// count the number of range in right subarray that have sum value fallen in [lower, upper]
int lowerIndex = mid + 1, upperIndex = mid + 1; // [lowerIndex, upperIndex) is the range of data in the right array that are within [lower, upper]
for (int k = lo; k <= mid; k++) {
while (lowerIndex <= hi && tmp[lowerIndex] - tmp[k] < lower) lowerIndex++;
while (upperIndex <= hi && tmp[upperIndex] - tmp[k] <= upper) upperIndex++;
result[0] += upperIndex - lowerIndex; // upperIndex exclusive
}
// start merge now
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (j > hi || (i <= mid && tmp[i] <= tmp[j])) {
prefixSum[k] = tmp[i++];
} else {
prefixSum[k] = tmp[j++];
}
}
}
// BST
/*
https://leetcode.com/problems/count-of-range-sum/discuss/78003/Java-BST-solution-averagely-O(nlogn)
*/
// Binary Index Tree
/*
https://leetcode.com/problems/count-of-range-sum/discuss/78006/Summary-of-the-Divide-and-Conquer-based-and-Binary-Indexed-Tree-based-solutions
*/
// Segment Tree
/*
https://leetcode.com/problems/count-of-range-sum/discuss/77987/Java-SegmentTree-Solution-36ms
*/
// Red-Black Tree
/*
https://leetcode.com/problems/count-of-range-sum/discuss/78005/Java-Red-Black-Tree-72-ms-solution
*/
}