难度：⭐⭐⭐
关键词：原地哈希，原地置换
本题可以通过直接排序来解决，时间复杂度为O(nlogn)。但是还有时间复杂度为O(n)的方法，而且题目要求最好能找到时间复杂度为Ｏ(n)且空间复杂度为O(1)的方法。
Tips：一般来说，采用数组存储，又要满足空间复杂度为O(1)的方法，就是要借助数组来辅助完成计算。
方法一，哈希，时间复杂度O(n)，空间复杂度为O(n)
这里的思路比较简单，因为是找第一个正整数，那么可以hash从1到n，超出这个范围的我们不关心，找第一个没有出现的就可以了。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
vector<int> hash(nums.size(), 0);
int min = INT_MAX, n = nums.size();
for(int i : nums)
if(i < min && i > 0) min = i;
// 如果正整数最小值比1还大，那就缺1
if(min > 1) return 1;
for(int i : nums)
if(i > 0 && i - min < n) hash[i-min] = 1;
for(int j = 0; j < n; j++)
if(hash[j] == 0) return min+j;
return min+n;
}
};
方法二，原地哈希，官方题解中给的思路，时间复杂度为O(n)，空间复杂度为O(1)。
这里的方法比较巧妙，跟方法一一样，出现在[1,n]范围之外的数字我们不关心，于是在这里把这些值都统一置为n+1。这样整个数组中，值的范围就是[1,n+1]。
对于数组中每个元素，它的值为a，如果这个值不是n+1，就把arr[|a|-1]置为负值，如果已经是负值了则不做操作。也就是说，在这个原地哈希中，arr[i] 为负值就说明 i+1 出现过。
上述操作做完以后，只需要从头到尾遍历一遍，找到第一个正数所在的位置i，然后返回i+1
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 先把范围在(-infi, 0] 和 [n+1, +infi) 区间内的值都改为 n+1;
for(int i = 0; i < nums.size(); i++)
if(nums[i] >= n+1 || nums[i] <= 0) nums[i] = n+1;
// 这样整个数组就都是正数了
for(int i = 0; i < nums.size(); i++){
if(abs(nums[i]) != n+1){
int temp = abs(nums[i]);
if(nums[temp - 1] > 0) nums[temp-1] *= -1;
}
}
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0) return i+1;
}
return n + 1;
}
};
方法三，置换，时间复杂度为O(n)，空间复杂度为O(1)。
这个方法是我想到的，之前做过类似的题目，这个与官方题解中的置换方法大致相同。
先把出现在[1,n]范围之外的数字都置为0。依旧是将数字[1,n]一一映射到区间[0,n-1]。
从头开始遍历数组，如果当前值arr[i]大于0，且arr[arr[i]]不为-1，就将arr[arr[i]]处置为-1，并将之前arr[arr[i]]赋给arr[i]，并且i--。
也就是说，直到arr[arr[i]]的值一开始就是-1，i才继续往下进行。
分析一下这里的算法时间复杂度，假设，从i=0，能依次找到所有的值，这里遍操作了n次，后面还有n-1个值为-1的元素，所有总共要遍历2n-1次，时间复杂度依旧是O(n)。因为操作是在原数组上完成的，空间复杂度为O(1)。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 先把出现在[1,n]之外的数字都置为0。
for(int i = 0; i < n; i++) if(nums[i] < 0 || nums[i] >= n+1) nums[i] = 0;
// 用数组下标0~n-1来映射1~n
// 如果这个数字出现了，就将其赋值为-1，没出现则赋值为0
for(int i = 0; i < n; i++)
if(nums[i] > 0){
int temp = nums[i]-1;
if(temp == i) nums[i] = -1;
else if(nums[temp] != -1){
nums[i] = nums[temp];
nums[temp] = -1;
i--;
}
}
for(int i = 0; i < n; i++) if(nums[i] != -1) return i+1;
return n+1;
}
};
难度：⭐
自己解决程度：能解决，但是用到的方法不好
虽然这道题是一个简单题，但是我的做法有点笨拙。我的想法是，根据右上角和左上角的值，来分别筛掉某一行和某一列，直到最后留下来的
int main(void){
// 读入数据
int n, m, k;
cin >> n >> m >> k;
cin.get();
vector<vector<int>> matrix (n, vector<int>(m, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> matrix[i][j];
}
cin.get();
}
// 处理
int ax = 0, ay = 0, bx = n-1, by = m-1;
bool res = false;
// 循环收缩A点与B点
while(ax != bx || ay != by){
if(ax < bx && matrix[ax][by] < k){
ax++;
}
else if(ay < by && matrix[bx][ay] < k){
ay++;
}
else if(ax < bx && matrix[bx][ay] > k){
bx--;
}
else if(ay < by && matrix[ax][by] > k){
by--;
}
if(matrix[ax][ay] == k
|| matrix[bx][by] == k
|| matrix[bx][ay] == k
|| matrix[ax][by] == k ) {
res = true;
break;
}
}
if (res) cout << "Yes";
else cout << "No";
return 0;
}
题解的方法更简单，它选择从右上角或者左下角开始遍历。
这样做的好处非常明显，以右上角为例，右上角遍历，如果当前值比目标值大，就向左移动，如果当前值比目标值小，就向下移动。可以证明这种走法是可靠的。
int main(void){
// 读入数据
int n, m, k;
cin >> n >> m >> k;
cin.get();
vector<vector<int>> matrix (n, vector<int>(m, 0));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> matrix[i][j];
}
cin.get();
}
// 处理
// 可以选择从右上角或者左下角开始遍历，这里选择右上角
int x = 0, y = n-1;
while(x >= 0 && x <= n-1 && y >= 0 && y <= n-1){
if(matrix[x][y] == k){
cout << "Yes";
return 0;
}
else if(matrix[x][y] > k) y--;
else x++;
}
cout << "No";
return 0;
}
这个题有三种解法，从时间复杂度越来越低，分别是动态规划法 $O(N^2)$ 、二分查找法 $O(NlogN)$ 和滑动窗口法 $O(N)$，根据Leetcode-487. 最大连续1的个数 II的经验，我首先用的是动态规划来做。
这里使用长度为K+1的数组 dp 来存储状态，然后根据当前的元素是0还是1，决定状态的更新。
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int ans = 0;
int len = K+1;
vector<int> dp (len, 0);
for(int a : A){
if(a == 1){
for(int i = 0; i < len; i++){
dp[i]++;
ans = max(ans, dp[i]);
}
}
else{
for(int i = len-1; i >= 1 ; i--){
dp[i] = dp[i-1] + 1;
ans = max(ans, dp[i]);
}
dp[0] = 0;
}
}
return ans;
}
};
正确性是没有问题的，因为题目的时间限制比较紧，所以超时了。
这里注意，不是所有的题，用了动态规划就一定是时间最优！！！
看了解答，才发现可以使用二分查找和滑动窗口来做。二分查找单独建立了一个专题，就不在这里赘述了，而且时间复杂度没有滑窗优。使用滑窗，只需要保证在窗口里面，有小于等于K个0。
class Solution {
public:
int longestOnes(vector<int>& A, int K) {
int i = 0, j = 0, res = 0, count = 0;
while(j < A.size()){
// cout << i << " " << j << endl;
if(count < K){
if(A[j] == 0) count++;
j++;
}
else if(count == K && A[j] == 1){
j++;
}
else{
while(true){
if(A[i] == 1) i++;
else{
i++;
count--;
break;
}
}
}
if(j-i > res) res = j - i;
}
return res;
}
};
本周的周赛也遇到了一道与上面的题相同的题，我也是一开始没有思路，然后使用了动态规划来做，但是遇到了问题，最后才想到使用滑窗来做，但是做完的时候已经超时了。
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int ans = 1; // 使用end-begin+1来对其进行更新
int begin = 0, end = 0;
long long cost = 0;
int len = nums.size();
while(end < len-1){
// 先无脑后移一位
end++;
// 计算cost
cost = cost + (long long)(nums[end] - nums[end-1]) * (end - begin);
if(cost <= k){
if(ans < end - begin + 1) ans = end - begin + 1;
}
while(cost > k){
cost -= (nums[end] - nums[begin]);
begin++;
}
}
return ans;
}
};
Leetcode-53 最大子序和
Leetcode-673 最长递增子序列的个数