本题使用了两次 partial sorting / std::nth_element 来进行部分排序，可以作为经典教程了。
速度比全排序或者heap/pq快到不知道哪里去了～
Time complexity: O(m*n)
Space complexity: O(m*n)
不用黑科技就达到99.77%
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) { // Step 1: Sort each row using fast parition, collect largest limits[i] elements. vector<int> nums; nums.reserve(grid.size() * grid[0].size()); for (int i = 0; i < grid.size(); ++i) { nth_element(begin(grid[i]), begin(grid[i]) + limits[i], end(grid[i]), std::greater{}); nums.insert(nums.end(), begin(grid[i]), begin(grid[i]) + limits[i]); } // Setp 2: fast partition to find the largest k elements. O(m*n). nth_element(begin(nums), begin(nums) + k, end(nums), std::greater{}); // Step 3: Sum them up. O(k) return accumulate(begin(nums), begin(nums) + k, 0LL); } }; |