本文为系统刷leetcode的记录，会记录自己根据代码随想录刷过的leetcode，方便直接点开刷题，时常更新 时间复杂度简记为s 空间复杂度简记为k
数组
704 二分查找 一维二分查找 （1）[left, right]
class Solution {
public:
int search(vector
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
};
s:
O
(
l
o
g
n
)
O(logn)
O(logn) k:
O
(
1
)
O(1)
O(1) （2）[left, right)
class Solution {
public:
int search(vector
int left = 0;
int right = nums.size();
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else return mid;
}
return -1;
}
};
s:
O
(
l
o
g
n
)
O(logn)
O(logn) k:
O
(
1
)
O(1)
O(1) 二维二分查找：74. 搜索二维矩阵
class Solution {
public:
bool searchMatrix(vector
int m = matrix.size();
int n = matrix[0].size();
int low = 0;
int high = m * n - 1;
while (low <= high) {
int mid = (low + high) / 2;
int num = matrix[mid / n][mid % n]; // 第一个是确定第几行，第二个是确定第几列，相当于把matrix降维成一维，比如要找一个4*4数组的第13个元素，13/4 = 3，为第四行（行索引是0开始），13%4=1，即第四行第一个
if (num < target) {
low = mid + 1;
} else if (num > target) {
high = mid - 1;
} else return true;
}
return false;
}
};
27. 移除元素
class Solution {
public:
int removeElement(vector
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
};
s：
O
(
n
)
O(n)
O(n) k：
O
(
1
)
O(1)
O(1)
977. 有序数组的平方
class Solution {
public:
vector
int k = nums.size() - 1;
vector
for (int i = 0, j = nums.size() - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
result[k--] = nums[i] * nums[i];
i++;
} else {
result[k--] = nums[j] * nums[j];
j--;
}
}
return result;
}
};
s：
O
(
n
)
O(n)
O(n) k：
O
(
n
)
O(n)
O(n) 209. 长度最小的子数组
59. 螺旋矩阵 II
推荐链接
您阅读本篇文章共花了：
发表评论