一刷 05/2020
Version #1 Binary Search - Not Optimal
Time O(n^2logn)
Space O(1)
class Solution {
public int triangleNumber(int[] nums) {
// triangle - given side lengths a <= b <= c, if a + b > c then they can make a triangle
// Brute force O(n^3)
// Binary search
// sort the array
// given a and b, find the largest index of c that can make a + b > c
if (nums == null || nums.length < 3) {
return 0;
}
int cnt = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
cnt += count(nums, i, j);
}
}
return cnt;
}
private int count(int[] nums, int i, int j) {
if (i >= j || j + 1 >= nums.length) {
return 0;
}
// find the largest index k that make nums[i] + nums[j] > nums[k]
// k > j && k < nums.length
int sum = nums[i] + nums[j];
int start = j + 1;
int end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= sum) {
end = mid - 1;
} else {
start = mid;
}
}
// From j + 1 to k, all nums[k] can form a triangle
// count = k - (j + 1) + 1 = k - j
if (nums[end] < sum) {
return end - j;
}
if (nums[start] < sum) {
return start - j;
}
return 0;
}
}
Version # Two Pointers
Time O(n^2)
Space O(1)
class Solution {
public int triangleNumber(int[] nums) {
// Assuming side lengths a <= b <= c, if a + b > c then they can form a triangle
// Iterate through nums to select a number c
// Try to find pairs on its left whose sum is larger than c
if (nums == null || nums.length < 3) {
return 0;
}
Arrays.sort(nums);
int cnt = 0;
// at least needs to be the 3rd number to have two numbers on its left
for (int i = 2; i < nums.length; i++) {
cnt += count(nums, i);
}
return cnt;
}
private int count(int[] nums, int targetIndex) {
int start = 0, end = targetIndex - 1;
int cnt = 0;
while (start < end) {
if (nums[start] + nums[end] > nums[targetIndex]) {
// for all start < end, nums[start] + nums[end] is larger than nums[targetIndex]
cnt += end - start;
end--;
} else {
start++;
}
}
return cnt;
}
}
No comments:
Post a Comment