每周算法-数组类算法

概述

作为一名程序员,对于数组都不陌生,可能第一个学习的数据结构就是它了。它作为一种线性的数据结构,通过索引可以直接获取到它的值,查询任意索引的时间复杂度是O(1), 插入任意位置的时间为O(n), 当然如果插入到其最后一位,那么它的时间复杂度就是O(1)。因此,这么一个看似这么简单的数据结构,当我们在求解某一些算法的过程中体验又如何呢?

对于数组来说,在求解的过程中,大致有两种思路。一种是多指针,最明显的就是快排,尤其像三路快排。另一种思路就是滑动窗口,遇到的最多的是求字符串的子串这种类型。这里说一下,其实抽象的来看,字符串和数组的区别不大,都是线性递增的一种数据结构,因此这里将其归为一类。

那么先来看第一种思路的题解。

leetcode 283. 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。必须在原数组上操作,不能拷贝额外的数组

  • 输入 [0,1,0,3,12]
  • 输出 [1,3,12,0,0]

对于这道题,我们可以理解为一个指针x初始指向最前面,代表非零元素的临界点, 则[0, x)表示非零元素。[x, len)表示0元素。

那看代码:

1
2
3
4
5
6
7
8
9
10
11
12
const moveZeroes = function(nums) {
let x = 0;
let len = nums.length;
for (let i = 0; i < len; i++) {
if (nums[i]) {
nums[x++] = nums[i];
}
}
for (let i = x; i < len; i++) nums[x++] = 0;

return nums;
}

leetcode 26题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

  • 输入 [0,0,1,1,1,2,2,3,3,4]
  • 输出 5 并且入参数组前5个元素为[0, 1, 2, 3, 4]

对于这道题其实是去重的一个子问题,这是有序的数组去重,我们需要一个指针x指向正确的非重复的元素,即[0, x]表示非重复元素,至于x之后的我们就可以不用在乎。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
const removeDuplicates = function(nums) {
const len = nums.length;
let currNum = nums[0];
let x = 0;
for (let i = 1; i < len; i++) {
if (currNum !== nums[i]) {
nums[++x] = nums[i];
currNum = nums[i];
}
}
return x + 1;
}

因此对于随机的数组,可以先用快排排序,之后去重即可删除任意数组的重复元素。

leetcode 215 在未排序的数组中找到第 k 个最大的元素, 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

  • 输入 [3,2,1,5,6,4] k = 2
  • 输出 5

    对于这道题,就是可以使用快排的思路来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const partition = (left, right, nums) => {
if (left >= right) return left;

const pivot = nums[left];
let x = left;
for (let i = left; i <= right; i++) {
if (nums[i] < pivot) {
nums[x++] = nums[i];
}
}
nums[x] = pivot;

return x;
};
const quickSort = (left, right, nums, k) => {
const p = partition(left, right, nums);
if (p < k) {
return quickSort(p + 1, right, nums, k);
} else if (p > k) {
return quickSort(left, p - 1, nums, k);
}
return nums[p];
};
var findKthLargest = function(nums, k) {
return quickSort(0, nums.length - 1, nums, nums.length - k);
}

对于第二种思路的解法:滑动窗口
滑动窗口也是使用两个指针left和right表示一个滑动窗口,窗口未包含需要的子串的时候,增大right指针,直到包含了子串的时候,增大left指针。

leetcode 76. 最小覆盖子串.给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串。

  • 输入 S = “ADOBECODEBANC”, T = “ABC”
  • 输出 “BANC”

这道题,我们首先想到的是应该有一个数组记录每个字母的出现的次数,当然还需要一个变量记录当前还需要多少个字符才能包含子串,当该变量为0的时候,此时窗口包含了子串,开始增大左指针。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
var minWindow = function(s, t) {
let ret = '';
const subStrLen = t.length
const len = s.length;

if (!s || !t || subStrLen > len) return ret;

const subStrFreq = {};
for (let i = 0; i < subStrLen; i++) {
if (subStrFreq[t[i]]) subStrFreq[t[i]]++;
else subStrFreq[t[i]] = 1;
}

let start = 0;
let end = -1;
let tLen = subStrLen;
// [start, end]
while (end < len - 1) {
// 滑动窗口中缺少该字符
if (subStrFreq[s[++end]] > 0) {
tLen--;
}

if (typeof subStrFreq[s[end]] === 'number') {
// 频率减1
subStrFreq[s[end]]--;
}

// 包含所有的子串的时候
while (tLen === 0) {
// 更新返回值
ret = (ret && ret.length < end + 1 - start) ? ret : s.slice(start, end + 1);

// 开始增大start值
// 当前start上的值属于子串的某个字符时
if (subStrFreq[s[start]] === 0) {
tLen++;
}

if (typeof subStrFreq[s[start]] === 'number') {
subStrFreq[s[start]]++;
}
start++;
}
}

return ret;
};
-->