public int findDuplicate(int[] nums) {
int lo = 1, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (findSmall(nums, mid)) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
private boolean findSmall(int[] nums, int target) {
int count = 0;
for (int num : nums) {
if (num <= target) {
count++;
}
}
return count <= target;
}
For problems such as 410, 875, 1011, 1231, it is hard to start. It has pre-conditions:
Choose data from an array
Must choose consecutively
Can be determined by "try out"
Asking for a "min" or "max" of the choice
The problem asks if can be divide the array by a number and having the min/max of this range. Search in a range between the max of all numbers and the sum of all numbers. Use a helper function to try all numbers of the range, and find the min/max.
Instead of trying all numbers, we can use binary search to quickly determine the result.
T: O(N*log(range_size)) S: O(1)
public int shipWithinDays(int[] weights, int D) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int w : weights) {
max = Math.max(max, w);
sum += w;
}
int left = max, right = sum;
while (left < right) {
int mid = left + (right - left) / 2;
if (canDivide(weights, mid, D)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/*
*Determine if the array can split into D continuous subarrays,
and each subarray sum can fit (<=) capacity
*/
private boolean canDivide(int[] weights, int capacity, int D) {
int sum = 0, count = 1;
for (int w : weights) {
if (sum + w > capacity) {
sum = 0;
if (count++ > D) return false;
}
sum += w;
}
return count <= D;
}
public int splitArray(int[] nums, int m) {
int sum = 0, max = Integer.MIN_VALUE;
for (int n : nums) {
sum += n;
max = Math.max(max, n);
}
int lo = max, hi = sum;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (canDivide(nums, mid, m)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
/*
*Determine if the array can split into m continuous subarrays,
and each subarray sum is smaller than sum val
*/
private boolean canDivide(int[] nums, int val, int m) {
int sum = 0, count = 1;
for (int n : nums) {
if (sum + n > val) {
count++;
sum = 0;
if (count > m) {
return false;
}
}
sum += n;
}
return true;
}
Divide the array into K continuous subarrays, maximize the min share of this array
public int maximizeSweetness(int[] sweetness, int K) {
int sum = 0, min = sweetness[0];
for (int n : sweetness) {
sum += n;
min = Math.min(min, n);
}
int L = min, R = sum;
while (L < R) {
int mid = L + (R - L + 1) / 2;
if (canDivide(sweetness, mid, K)) {
L = mid;
} else {
R = mid - 1;
}
}
return L;
}
private boolean canDivide(int[] sweet, int t, int K) {
int groupcount = 0, sum = 0;
for (int n : sweet) {
sum += n;
if (sum >= t) {
groupcount++;
sum = 0;
}
}
return groupcount > K;
}
public int minEatingSpeed(int[] piles, int H) {
int right = 0;
for (int pile : piles) {
right = Math.max(right, pile);
}
int left = 0;
while (left < right) {
int mid = left + (right - left) / 2;
if (canEatAll(piles, H, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canEatAll(int[] piles, int h, int k) {
int hours = 0;
for (int p : piles) {
hours += Math.ceil(1.0 * p / k);
}
return hours <= h;
}
public double minmaxGasDist(int[] stations, int k) {
double left = 0, right = 1e8;
while (right - left > 1e-6) {
double mid = (left + right) / 2.0;
if (isValid(stations, k, mid)) {
right = mid;
} else {
left = mid;
}
}
return left;
}
private boolean isValid(int[] stations, int k, double d) {
int used = 0;
for (int i = 0; i < stations.length - 1; i++) {
used += (int) ((stations[i + 1] - stations[i]) / d);
}
return used <= k;
}