Description:
https://leetcode.com/problems/valid-triangle-number/description/
Algorithm1:
Use for loop for three times.
It works but slow (beats 23.60%)
Code1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public: int triangleNumber(vector& nums) { if (nums.size() < 3) return 0; int result = 0; sort(nums.begin(), nums.end()); int threshold; for (int i = 0; i < nums.size() - 2; i++) { for (int j = i + 1; j < nums.size() - 1; j++) { threshold = nums[i] + nums[j]; for (int k = j + 1; k < nums.size(); k++) { if (nums[k] < threshold) result++; else break; } } } return result; } }; |
Timing & Space:
O(n^3) & O(1)
Algorithm2:
Code2:
|
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 |
class Solution { public: int triangleNumber(vector& nums) { long n = nums.size(); int i, j, k; int total, a, b, c; if (n < 3) return 0; vector ct(1001, 0), sum(2001, 0); vector<pair<long, long>> p; for (i = 0; i < n; i++) ct[nums[i]]++; sum[0] = 0; // 0 cannot form triangle for (i = 1; i <= 1000; i++) sum[i] = sum[i - 1] + ct[i]; p.clear(); for (i = 1; i <= 1000; i++) if (ct[i] > 0) p.push_back(make_pair(i, ct[i])); for (i = 1001; i <= 2000; i++) sum[i] = sum[1000]; c = p.size(); total = 0; for (a = 0; a < c; a++) { if (p[a].second >= 2) { // a = b < c; total += (sum[p[a].first * 2 - 1] - sum[p[a].first]) * (p[a].second * (p[a].second - 1) / 2); // a = b = c if (p[a].second > 2) total += (p[a].second * (p[a].second - 1) / 2 * (p[a].second - 2) / 3); } for (b = a + 1; b < c; b++) { // a < b < c total += (sum[p[a].first + p[b].first - 1] - sum[p[b].first]) * p[a].second * p[b].second; // a < b = c if (p[b].second > 1) total += p[a].second * (p[b].second * (p[b].second - 1) / 2); } } return total; } }; |
Timing & Space:
Time:
Worst: O(n^2)
Best: O(1)
Space: O(1)