right..right..searching for the 3rd elem takes logn in a treemap, so n^2 * logn, not cool, not cool at all. Thanks man
chongli
@chongli
Posts made by chongli

RE: Hashmap c++ solution, quadratic time, 72ms

RE: Clean and short Merge sort Solution in c++
Neat solution indeed, but you're not using constant space to do mergesort. Recursive call need more space.

Hashmap c++ solution, quadratic time, 72ms
I assume all the solutions are like (x, y, z) and x <= y <= z, so no duplicate.
First scan the array into a map, so the keys are sorted.
Then outer loop the first element x, and inner loop the second y, and use map to find z.class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result(0); // scan the array into a map, record the occurrence map<int, int> m; for (int i = 0; i < nums.size(); ++i){ if (m.find(nums[i]) == m.end()) m[nums[i]] = 1; else ++m[nums[i]]; } typedef map<int, int>::iterator map_it; // OUTER LOOP on x, start from the front for (map_it iter = m.begin(); iter != m.end(); ++iter){ if (iter>first > 0) break; // if the minimum is greater than 0, no more solutions iter>second = 1; // keep track on the occurrence // INNER LOOP on y, start from where x stays for (map_it jter = iter; jter != m.end(); ++jter){ if (jter>second == 0) continue; // no more to use, continue int z = (iter>first + jter>first); jter>second = 1; // keep track on the occurrence // if we find the third elem, make sure it's max, and it's ok to use map_it temp = m.find(z); if (temp != m.end()){ if (z >= jter>first && temp>second != 0) { result.push_back({iter>first, jter>first, z}); } } jter>second += 1; // recover the occurrence } iter>second += 1; // recover the occurrence } return result; } };

RE: Confused. why heapsort on finding kth largest takes O(k*logn)
Thanks for the comments, but chill out man, why you getting so upset.

RE: Confused. why heapsort on finding kth largest takes O(k*logn)
I got this idea from other comments under this question, some even with a great many up votes. I just don't get it man.

RE: Confused. why heapsort on finding kth largest takes O(k*logn)
Er.. you sure about this? As far as I know, priority queue are often implemented with heaps, and building a heap either max heap or min heap, takes linear time.

Confused. why heapsort on finding kth largest takes O(k*logn)
Please enlighten me, guys
Extract the kth maximum from max heap takes O(klogn). I think I got this, because you have to extract the max element, max heapify the rest, then extract the second to max, max heapify the rest, so on so forth. Extract the max takes O(1), max heapifiy takes O(logn), which gives us O(klogn), because we have to do it k times.
However building a max heap from an unsorted array takes O(n) on average, so building part is more expensive than the finding max part, O(k*logn).
So take the both parts in total, it's the same timecomplexity as the quicksortlike algo, O(n)

RE: Share my O(m+n) solution
O(log(m + n)) requires more than classical merge sort.. only conqure and divide can give you log complexity

RE: My accepted insertion sort in C++
I'm afraid you implementation is not an insertion sort, pal. More like a bubble sort.