What is the time complexity of this method? O(N) or O(NlogN)? Thanks
Z
zengrui184
@zengrui184
8
Reputation
20
Posts
114
Profile views
0
Followers
0
Following
Posts made by zengrui184

RE: Simple C++ solution with priority queue

RE: C++ straightforward recursive solution
You could use
word.replace(i, j, to_string(j));
which is faster, I think 
RE: Straight forward C++ solution with explaination
I think it is Moore's Voting Algorithm of finding the Majority Element, in the first pass the person who is known by most other people stands out. Then we check whether everyone knows him and he knows no one in the second pass.

RE: C++ solution, using priority queue, O(n) time, O(k) space
Hi, I have the same idea, but why the time complexity is O(n)? Thanks!

RE: Sharing my 12ms C++ solution
You could use binary search to optimize your code, I think
void binarySearch(TreeNode* root, const double &target, double &diff, int &closest){ if(!root) return; double temp = abs(root>val  target); if(diff > temp){ closest = root>val; diff = temp; } if(root>val > target) binarySearch(root>left, target, diff, closest); else binarySearch(root>right, target, diff, closest); } int closestValue(TreeNode* root, double target) { double diff = LONG_MAX; int closest = root>val; binarySearch(root, target, diff, closest); return closest; }

RE: C++, O(n log n), 584+ ms, 3 solutions
My solution using priority queue, 584ms
static bool cmpStart(Interval x, Interval y){ return x.start < y.start; } int minMeetingRooms(vector<Interval>& intervals) { if(intervals.size() == 0) return 0; sort(intervals.begin(), intervals.end(), cmpStart); int cnt = 1; priority_queue<int, vector<int>, std::greater<int>> pq; pq.push(intervals[0].end); for(int i = 1; i < intervals.size(); ++i){ if(pq.top() <= intervals[i].start) pq.pop(); pq.push(intervals[i].end); cnt = max(cnt, (int)pq.size()); } return cnt; }

RE: C++ easy understand solution
Same idea
int shortestDistance(vector<string>& words, string word1, string word2) { int index1 = 1, index2 = 1, min_distance = INT_MAX; for(int i = 0; i < words.size(); ++i){ if(words[i].compare(word1) == 0) index1 = i; else if(words[i].compare(word2) == 0) index2 = i; else continue; if(index1 != 1 && index2 != 1) min_distance = min(min_distance, abs(index1  index2)); } return min_distance; }

RE: What is the algorithm that runs 4ms for C++?
I am not sure but surprised my two pointers solution got 4 ms AC.
vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right = numbers.size()  1; vector<int> res; while(left < right){ long long val = numbers[left] + numbers[right]; if(val == target){ res.push_back(left + 1); res.push_back(right + 1); break; }else if(val < target) left++; else right; } return res; }

RE: Simply 0ms C++ solution
I like your code, very concise and neat! It's more like two pointers