数组算法¶
1. 二分查找¶
核心点
- 有序数组
- 将目标值与数组中间元素进行比较,从而排除掉一半的元素,如此循环,直到找到目标值或确定目标值不存在
- 通常时间复杂度:\(O(logn)\)
其中需要注意:
- 区间范围决定了边界(包含起始位置)的值,可通过构造简单的有序数组来演算进行理解
1.1 算法:二分法¶
代码模版(点击展开)
1.2 相关题目¶
- 704二分查找
- 35.搜索插入位置
- 34.在排序数组中查找元素的第一个和最后一个位置
- 69.x 的平方根
- 367.有效的完全平方数
2. 移除元素¶
对应 LeetCode 题目:
Note
数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
若采取暴力解法,则类似于冒泡排序进行两层遍历,下面重点说明双指针法。
2.1 算法:双指针法¶
双指针法(快慢指针法):
- 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
定义快慢指针:
- 快指针:寻找新数组的元素,新数组就是不含有目标元素的数组
- 慢指针:指向更新新数组下标的位置
此思路不仅应用在数组中,在其他如链表、字符串等都有相应应用。
下面两个解法均可满足题意,后者的优点在于确保移动的最小次数
- 时间复杂度:\(O(n)\)
- 空间复杂度:\(O(1)\)
Go
func removeElement(nums []int, val int) int {
leftIdx, rightIdx := 0, len(nums)-1
for leftIdx <= rightIdx {
for leftIdx <= rightIdx && nums[leftIdx] != val {
leftIdx++
}
for leftIdx <= rightIdx && nums[rightIdx] == val {
rightIdx--
}
if leftIdx < rightIdx {
nums[leftIdx] = nums[rightIdx]
leftIdx++
rightIdx--
}
}
return leftIdx
}
2.2 相关题目¶
- 27.移除元素
- 26.删除排序数组中的重复项
- 283.移动零
- 844.比较含退格的字符串
- 977.有序数组的平方
3.长度最小的子数组¶
对应 LeetCode 题目:
Note
涉及到连续子数组的处理,可考虑使用滑动窗口的算法思想来解决
若采取暴力解法,则是通过两层循环不断寻找符合条件的子序列,下面重点说明滑动窗口解法。
3.1 算法:滑动窗口¶
滑动窗口的主要思想:
- 不断的调节子序列的起始位置和终止位置,从而得出预期结果
滑动窗口的实现通常需要确认如下三点:
- 窗口内是什么?
- 满足其和≥s的长度最小的连续子数组
- 如何移动窗口的起始位置?
- 若当前窗口的值大于s则窗口需要向前移动了
- 如何移动窗口的结束位置?
- 窗口的结束位置就是遍历数组的指针
具体实现代码如下: 时间复杂度:\(O(n)\) ,空间复杂度:\(O(1)\)
Go
func minSubArrayLen(target int, nums []int) int {
start, end := 0, 0
result := len(nums) + 1
cur := 0
for ; end < len(nums); end++ {
cur += nums[end]
for ; cur >= target; start++ {
result = min(result, end-start+1)
cur -= nums[start]
}
}
if result == len(nums)+1 {
return 0
}
return result
}
3.2 相关题目¶
- 209.长度最小的子数组
- 904.水果成篮
- 76.最小覆盖子串
4. 螺旋矩阵II¶
对应 LeetCode 题目:
Note
此题重要的不是算法,而是考察模拟的过程
4.1 算法:模拟过程¶
在上面提到二分法的时候就提到,如果要写出正确的二分法一定要坚持循环不变量原则。
而求解此题依然是要坚持循环不变量原则,模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
这里我们就需要保持循环不变量,保持每条边左闭右开的原则,具体代码如下:
时间复杂度:\(O(n^2)\),空间复杂度:\(O(1)\)
Go
func generateMatrix(n int) [][]int {
result := make([][]int, n)
for i, _ := range result {
result[i] = make([]int, n)
}
startX, startY := 0, 0
mid := n / 2
count, offset := 1, 1
for loop := n / 2; loop > 0; loop-- {
i, j := startX, startY
for j = startY; j < n-offset; j++ {
result[startX][j] = count
count++
}
for i = startX; i < n-offset; i++ {
result[i][j] = count
count++
}
for ; j > startY; j-- {
result[i][j] = count
count++
}
for ; i > startX; i-- {
result[i][j] = count
count++
}
startX++
startY++
offset++
}
if n%2 > 0 {
result[mid][mid] = count
}
return result
}
Rust
impl Solution {
pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
let mut result = vec![vec![0; n as usize]; n as usize];
let (mut start_x, mut start_y) = (0, 0);
let mid = (n / 2) as usize;
let (mut offset, mut count) = (1, 1);
for _ in (0..(n / 2)).rev() {
let (mut i, mut j) = (start_x, start_y);
for _ in start_y..(n as usize - offset) {
result[start_x][j] = count;
count += 1;
j += 1;
}
for _ in start_x..(n as usize - offset) {
result[i][j] = count;
count += 1;
i += 1;
}
for _ in 0..(j - start_y) {
result[i][j] = count;
count += 1;
j -= 1;
}
for _ in 0..(i - start_x) {
result[i][j] = count;
count += 1;
i -= 1;
}
start_x += 1;
start_y += 1;
offset += 1;
}
if n % 2 > 0 {
result[mid][mid] = count;
}
result
}
}
4.2 相关题目¶
- 54.螺旋矩阵
- 59.螺旋矩阵II
- 剑指Offer29.顺时针打印矩阵