April 14, 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; } }; |
数据规模比较大，算法必须是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); }); } }; |
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs(i, j)where0 <= i < j < nandnums[i] + nums[j] < target.
Example 1:
Input: nums = [-1,1,2,3,1], target = 2 Output: 3 Explanation: There are 3 pairs of indices that satisfy the conditions in the statement: - (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target - (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target - (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.
Example 2:
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2 Output: 10 Explanation: There are 10 pairs of indices that satisfy the conditions in the statement: - (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target - (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target - (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target - (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target - (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target - (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target - (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target - (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target - (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target - (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target
Constraints:
1 <= nums.length == n <= 50-50 <= nums[i], target <= 50Enumerate all pairs.
Time complexity: O(n2)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int countPairs(vector<int>& nums, int target) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) ans += nums[i] + nums[j] < target; return ans; } }; |
Sort the numbers.
Use two pointers i, and j.
Set i to 0 and j to n – 1.
while (nums[i] + nums[j] >= target) –j
then we have nums[i] + nums[k] < target (i < k <= j), in total (j – i) pairs.
++i, move to the next starting number.
Time complexity: O(nlogn + n)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int countPairs(vector<int>& nums, int target) { const int n = nums.size(); sort(begin(nums), end(nums)); int ans = 0; for (int i = 0, j = n - 1; i < n; ++i) { while (j >= i && nums[i] + nums[j] >= target) --j; ans += max(0, j - i); } return ans; } }; |
You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.
Return the maximum sum or -1 if no such pair exists.
Example 1:
Input: nums = [51,71,17,24,42] Output: 88 Explanation: For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88. For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66. It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.
Example 2:
Input: nums = [1,2,3,4] Output: -1 Explanation: No pair exists in nums with equal maximum digits.
Constraints:
2 <= nums.length <= 1001 <= nums[i] <= 104Enumerate all pairs of nums and check their sum and max digit.
Time complexity: O(n2)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua class Solution { public: int maxSum(vector<int>& nums) { auto maxDigit = [](int x) { int ans = 0; while (x) { ans = max(ans, x % 10); x /= 10; } return ans; }; int ans = -1; const int n = nums.size(); for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (nums[i] + nums[j] > ans && maxDigit(nums[i]) == maxDigit(nums[j])) ans = nums[i] + nums[j]; return ans; } }; |