标签：映射 nums int height vector include 指针
双指针
#include <vector>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n)，额外空间复杂度 O(1)
vector<int> sortArrayByParityII(vector<int> &nums) {
int even = 0;
int odd = 1;
while (even < nums.size() - 1 && odd < nums.size()) {
// 找到偶数下标，但元素是奇数的位置
while (even < nums.size() - 1 && ((nums[even] & 1) == 0)) even += 2;
// 找到奇数下标，但元素是偶数的位置
while (odd < nums.size() && ((nums[odd] & 1) != 0)) odd += 2;
// 交换
if (even < nums.size() - 1 && odd < nums.size()) swap(nums[even], nums[odd]);
}
return nums;
}
};
- 要求 不修改 数组
nums 且只用常量级 O(1) 的额外空间。
#include <vector>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n)，额外空间复杂度 O(1)
// 类似环形链表找入口节点，nums 数组类似静态链表
int findDuplicate(vector<int> &nums) {
int slow = 0, fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while (slow != fast) {
// slow = slow.next
slow = nums[slow];
// fast = fast.next.next
fast = nums[nums[fast]];
}
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
};
#include <vector>
using namespace std;
class Solution {
public:
// 按行累积，每次累加当前行上能接多少水（超时）
int trap(vector<int> &height) {
int n = height.size();
// 找最大高度
int maxHeight = 0;
for (const auto &item: height)
maxHeight = max(maxHeight, item);
int res = 0;
// 每次找一层，一格一格的加
for (int level = 1; level <= maxHeight; ++level) {
int i = 0;
// 找到第一个不低于当前 lever 的作为左边界
while (i < n && height[i] < level) i++;
// 找不到左边界，这层以及上面的层都接不了水
if (i >= n) break;
for (int water = 0; i < n; i++) {
if (height[i] < level) {
// 已有左边界，并且比当前层低，说明这个格子 (i, lever) 可以放水
water++;
} else if (height[i] >= level) {
// 找到大于或等于当前层的右边界，就把之前累积的水加到结果中，并清空 water
// 当前的右边界变成下一个左边界，在继续寻找下一个右边界
res += water;
water = 0;
}
}
}
return res;
}
};
#include <vector>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n)，额外空间复杂度 O(n)
// 按列累积，每次累加当前列上能接多少水
int trap(vector<int> &height) {
int n = height.size();
int res = 0;
// 记录当前元素左边的最大值
int leftMax = height[0];
// 可以在后续累积雨水时遍历数组的操作中，用 leftMax 优化掉 leftMaxArr
vector<int> leftMaxArr(n);
// 更新每个元素左边的最大值
for (int i = 1; i <= n - 2; ++i) {
leftMaxArr[i] = leftMax;
leftMax = max(leftMax, height[i]);
}
// 记录当前元素右边的最大值
int rightMax = height[n - 1];
vector<int> rightMaxArr(n);
for (int i = n - 2; i >= 1; i--) {
rightMaxArr[i] = rightMax;
rightMax = max(rightMax, height[i]);
}
// 只有左边最高的和右边最高的，二者中的较小者比当年的列高，当前列才能接得住水
for (int i = 1; i <= n - 2; ++i)
res += max(0, min(leftMaxArr[i], rightMaxArr[i]) - height[i]);
return res;
}
};
- 双指针优化掉 leftMaxArr、rightMaxArr（最优解）
#include <vector>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n)，额外空间复杂度 O(1)
int trap(vector<int> &height) {
int n = height.size();
int l = 1;
int r = n - 2;
// 左边最高
int lMax = height[0];
// 右边最高
int rMax = height[n - 1];
int res = 0;
while (l <= r) {
if (lMax <= rMax) {
// 左边的最高柱子较低些
res += max(0, lMax - height[l]);
lMax = max(lMax, height[l++]);
} else {
// 右边的最高柱子较低些
res += max(0, rMax - height[r]);
rMax = max(rMax, height[r--]);
}
}
return res;
}
};
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int trap(vector<int> &height) {
int res = 0;
stack<int> stk;
for (int i = 0; i < height.size(); i++) {
// 当前高度大于栈顶高度，说明之前的地方有可能能接水
// 持续出栈，直到栈顶高度大于等于当前高度或者栈为空
while (!stk.empty() && height[i] > height[stk.top()]) {
int top = height[stk.top()];
stk.pop();
if (stk.empty()) break;
// 两个柱子间的距离，不包含两端
int distance = i - stk.top() - 1;
// height[stk.top()] 为左边界，height[i] 为右边界
int smaller = min(height[stk.top()], height[i]);
res += distance * (smaller - top);
}
stk.emplace(i);
}
return res;
}
};
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n * logn)，因为有排序，额外空间复杂度 O(1)
int numRescueBoats(vector<int> &people, int limit) {
sort(people.begin(), people.end());
int res = 0;
for (int l = 0, r = people.size() - 1; l <= r; res++) {
int sum = l == r ? people[l] : people[l] + people[r];
// 如果没超重，最轻的可以和最重的共用一条船
if (sum <= limit) l++;
r--;
}
return res;
}
};
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n)，额外空间复杂度 O(1)
int maxArea(vector<int> &height) {
int res = 0;
for (int l = 0, r = height.size() - 1; l < r;) {
int water = (r - l) * min(height[l], height[r]);
res = max(res, water);
// 每次把短板往中间靠，短板可能变长，总面积才可能变大
// 如果移动长板，底一定变小，高度不会超过之前的那个短板，高只会原来越低，面积只会变小
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return res;
}
};
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 返回当前的地点 houses[i] 由 heaters[j] 来供暖是否是最优
// 当前的地点 houses[i] 由 heaters[j] 来供暖，产生的半径是a
// 当前的地点 houses[i] 由 heaters[j + 1] 来供暖，产生的半径是 b
// 如果 a < b, 说明是最优，供暖不应该跳下一个位置
// 如果 a >= b, 说明不是最优，应该跳下一个位置
bool best(vector<int> &houses, vector<int> &heaters, int i, int j) {
return j == heaters.size() - 1
|| abs(heaters[j] - houses[i]) < abs(heaters[j + 1] - houses[i]);
}
// 时间复杂度 O(n * logn)，因为有排序，额外空间复杂度 O(1)
int findRadius(vector<int> &houses, vector<int> &heaters) {
sort(houses.begin(), houses.end());
sort(heaters.begin(), heaters.end());
int res = 0;
// i 号房屋，j 号供暖器
for (int i = 0, j = 0; i < houses.size(); i++) {
while (!best(houses, heaters, i, j)) j++;
res = max(res, abs(heaters[j] - houses[i]));
}
return res;
}
};
- 原地映射：把值为 value 的元素映射到数组中下标为 value - 1 的位置
#include <vector>
using namespace std;
class Solution {
public:
// 原地映射：把值为 value 的元素映射到数组中下标为 value-1 的位置
// 优化了对映射后覆盖掉的值的处理
int firstMissingPositive(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
// 如果 nums[i] 也能映射到数组中，并且尚未映射过
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
// 把 nums[i] 映射到 nums[nums[i] - 1]，nums[nums[i] - 1] 放在 nums[i]
// 然后继续判断新的 nums[i] 是否也需要映射
swap(nums[nums[i] - 1], nums[i]);
}
}
// 遍历寻找第一个空缺
for (int i = 0; i < n; ++i)
if (nums[i] != i + 1)
return i + 1;
// 重新映射后，数组中没有空缺，说明缺失的第一个正数就是 n + 1
return n + 1;
}
};
#include <vector>
#include <valarray>
using namespace std;
class Solution {
public:
// 原地映射：把可以映射到的地方的元素改成负数，映射规则还是 value 映射到 nums[value-1]
int firstMissingPositive(vector<int> &nums) {
int n = nums.size();
// 非正数改成 n + 1
for (int i = 0; i < n; ++i)
if (nums[i] <= 0)
nums[i] = n + 1;
for (int i = 0; i < n; ++i) {
// 待映射的值
int value = abs(nums[i]);
// 如果可以映射到数组里，就把映射到的地方的元素改成负数
if (value <= n) nums[value - 1] = -abs(nums[value - 1]);
}
for (int i = 0; i < n; ++i)
if (nums[i] > 0)
return i + 1;
return n + 1;
}
};
#include <vector>
using namespace std;
class Solution {
public:
// 时间复杂度 O(n)，额外空间复杂度 O(1)
int firstMissingPositive(vector<int> &nums) {
// [0, l) 为已经映射的区域，l 是待处理的位置
int l = 0;
// [r, ...) 为无法映射的区域
// r 的第二个含义是这 r 个数最好的情况下能映射到 [0, r-1]
// 当有一个数字无法映射的时候，就剩下 r-1 个待映射的，最好情况下能映射到 [0, r-2]
int r = nums.size();
// [l, r) 为待映射的区域
while (l < r) {
if (nums[l] == l + 1) {
// 已经映射好了，已映射区域右扩
l++;
} else if (nums[l] <= l || nums[l] > r || nums[nums[l] - 1] == nums[l]) {
// 把映射不了的数字或者重复出现的数字，与后面待映射的数字交换，无法映射的区域左扩
// nums[l] <= l 说明 nums[l] 已经映射好了，已经映射的区域中有重复
// nums[l] > r 说明无法映射
// nums[nums[l] - 1] == nums[l] 也是说明 nums[l] 已经映射好了，待映射区域中有重复
swap(nums[l], nums[--r]);
} else {
// 可以映射
swap(nums[l], nums[nums[l] - 1]);
}
}
return l + 1;
}
};
标签：映射,
nums,
int,
height,
vector,
include,
指针
From： https://www.cnblogs.com/sprinining/p/18450731