每周算法-数组类算法

发表于 |

概述

作为一名程序员，对于数组都不陌生，可能第一个学习的数据结构就是它了。它作为一种线性的数据结构，通过索引可以直接获取到它的值，查询任意索引的时间复杂度是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;
};
-->