April 13, 2025
最直接的方法就是扫描三遍，<, = , > pivot。
时间复杂度：O(n)
空间复杂度：O(1) // no extra space used except for output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: vector<int> pivotArray(vector<int>& nums, int pivot) { vector<int> ans; for (int x: nums) if (x < pivot) ans.push_back(x); for (int x : nums) if (x == pivot) ans.push_back(x); for (int x : nums) if (x > pivot) ans.push_back(x); return ans; } }; |
数据规模 n <= 1000。O(n2) 的算法也是能过的。
方法1: Brute Force
双重循环枚举所有的(nums[i], nums[j])的组合。
时间复杂度：O(n2)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) ans = max(ans, nums[j] - nums[i]); return ans ? ans : -1; } }; |
方法2: 空间换时间
使用prefix sum算法，预先计算num[i] ~ nums[n-1]的最大值，存储在right[i]中。
时间复杂度：O(n)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; vector<int> right(n, nums.back()); for (int i = n - 2; i >= 0; --i) right[i] = max(right[i + 1], nums[i]); for (int i = 0; i < n; ++i) ans = max(ans, right[i] - nums[i]); return ans ? ans : -1; } }; |
方法3: Running Min
从左到右遍历，记录当前为止出现过最小的值。比较 nums[i] – 最小值 和 最优解。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; int smallest = nums[0]; for (int i = 1; i < n; ++i) { ans = max(ans, nums[i] - smallest); smallest = min(smallest, nums[i]); } return ans ? ans : -1; } }; |
数据规模比较大，算法必须是O(n)的。
可以预先使用O(n)时间计算nums[0] .. nums[i]的最大值，存在left[i]中，以及nums[i] .. nums[n-1]的最小值存在right[i]中。然后再按题目的定义计算即可。
时间复杂度：O(n)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: int sumOfBeauties(vector<int>& nums) { const int n = nums.size(); vector<int> left(n, nums[0]); vector<int> right(n, nums.back()); for (int i = 1; i < n; ++i) left[i] = max(left[i - 1], nums[i]); for (int i = n - 2; i >= 0; --i) right[i] = min(right[i + 1], nums[i]); int ans = 0; for (int i = 1; i < n - 1; ++i) if (left[i - 1] < nums[i] && nums[i] < right[i + 1]) ans += 2; else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) ans += 1; return ans; } }; |
不太喜欢这样的题目，你需要证明/猜测最优解是将所有数字转换成median/中位数。
使用nth_element找中位数，然后再循环一遍求合即可。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int minMoves2(vector<int>& nums) { const int n = nums.size(); nth_element(begin(nums), begin(nums) + n / 2, end(nums)); const int median = nums[n / 2]; return accumulate(begin(nums), end(nums), 0, [median](int s, int x) { return s + abs(x - median); }); } }; |
本题使用了两次 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); } }; |