05 August 2008
找出正整数数组中乘积小于k的所有子数组
二分 - O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k == 0) return 0;
double logk = Math.log(k);
double[] prefix = new double[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefix[i+1] = prefix[i] + Math.log(nums[i]);
}
int ans = 0;
for (int i = 0; i < prefix.length; i++) {
int lo = i + 1, hi = prefix.length;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (prefix[mi] < prefix[i] + logk - 1e-9) lo = mi + 1;
else hi = mi;
}
ans += lo - i - 1;
}
return ans;
}
}
双指针 - O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int result = 0;
if (k <= 1) { //需要保证数组里元素都是正数
return result;
}
int left = 0;
int product = 1;
for (int right = 0; right < nums.length; right++) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
result += right - left + 1; //left到right之间满足条件的"增量"数组的数量
}
return result;
}
}