17 天算法挑战（2）二分、归并、中位数、寻路

Pluveto

Nov 10, 2021 发布

? 次浏览

今日目标

二分查找
二叉搜索树
合并排序
正序数组的中位数
Huffman 树构造
Dijkstra 算法
A* 算法

二分查找

标准二分查找

即不在乎位置是第几次出现。比如 1,2,2,3 中找 2，则返回 1 或者 2 都可以。

class Solution {
public:
  int searchInsert(vector<int> &v, int target) {
    auto i_hi = v.size() - 1;
    auto i_lo = 0;
    auto i_md = 0;
    while (i_lo != i_hi + 1) {
      i_md = i_lo + (i_hi - i_lo) / 2;
      if (v[i_md] == target) {
        return i_md;
      }
      if (v[i_md] < target) {
        i_lo = i_md + 1;
      } else
        i_hi = i_md - 1;
    }
    return i_lo;
  }
};

寻找上下确界

最朴素的方法就是，先按照普通方法找到一个，然后上下试探：

#include <debug.h>

class Solution {
  int binary_search(vector<int> &v, int target) {
    auto i_hi = v.size() - 1;
    auto i_lo = 0;
    auto i_md = 0;
    while (i_lo != i_hi + 1) {
      i_md = i_lo + (i_hi - i_lo) / 2;
      if (v[i_md] == target) {
        return i_md;
      }
      if (v[i_md] < target) {
        i_lo = i_md + 1;
      } else
        i_hi = i_md - 1;
    }
    return -1;
  }
  int search_first(vector<int> &v, int target) {
    if (v.size() == 0)
      return -1;
    auto i = binary_search(v, target);
    if (i == -1) {
      return -1;
    }
    while (0 <= i - 1 && i - 1 <= v.size() - 1 && v[i - 1] == target) {
      i--;
    }
    return i;
  }

  int search_last(vector<int> &v, int target) {
    if (v.size() == 0)
      return -1;
    auto i = binary_search(v, target);
    if (i == -1) {
      return -1;
    }
    while (0 <= i + 1 && i + 1 <= v.size() - 1 && v[i + 1] == target) {
      i++;
    }
    return i;
  }

public:
  vector<int> searchRange(vector<int> &nums, int target) {
    return {search_first(nums, target), search_last(nums, target)};
  }
};

int main(int argc, char const *argv[]) {
  Solution s;
  vector<int> v = {5, 7, 7, 8, 8, 10};
  auto ret = s.searchRange(v, 8);
  print_vec(ret);

  vector<int> v2 = {1, 2, 3, 3, 3, 2, 1};
  auto ret2 = s.searchRange(v2, 3);
  print_vec(ret2);

  vector<int> v3 = {2, 2};
  auto ret3 = s.searchRange(v3, 3);
  print_vec(ret3);
  return 0;
}

终极解法

下面介绍五点七边的视频二分查找为什么总是写错提到的方法。

模板：

  int binary_search(vector<int> v, int target) {
    int l = -1, r = v.size ();      // 初始条件 l,r 分处边界外。
    while (l + 1 != r) {           // 交叉终止 
      int mid = l + (r - l) / 2;
      if (v [mid] <target) {       // 等号有无决定了目标区的左右归属。有等号，则归属左边。
        l = mid;
      } else {
        r = mid;
      }
    }
    return l;                      // 返回的左右对应了分界线的左右
  }

二分查找的可以看作 L, R 两个区域的边界扩张。每次争夺到的位置用 mid 标记，当两方势力交叉时，循环终止。再也不用死记硬背啦！

对于 P34，用这种方法的解法：

class Solution {

public:
  // 我们要取得的是 {1, 2, 2, 2, 3} 中的第一个 2
  // 那么最后的格局是： {1}{2,2,2,3}，取 r
  // 因此 r 的扩张要更强势，即不带等号（等号相当于优先扩张 l）
  int search_first(vector<int> &v, int target) {
    int l = -1, m, r = v.size();
    while (l + 1 != r) {
      m = (r - l) / 2 + l;
      if (v[m] < target) {
        l = m;
      } else {
        r = m;
      }
    }
    return r;
  }
  // 我们要取得的是 {1, 2, 2, 2, 3} 中的最后一个 2
  // 即最后的格局是 {1,2,2,2}{3}，取 l
  // 那么 l 的扩张更强势
  int search_last(vector<int> &v, int target) {
    int l = -1, m, r = v.size();
    while (l + 1 != r) {
      m = (r - l) / 2 + l;
      // 小于目标值，说明下界给得太小，所以扩张 l
      if (v[m] <= target) {
        l = m;
      } else {
        r = m;
      }
    }
    return l;
  }

  vector<int> searchRange(vector<int> &nums, int target) {
    if (nums.empty())
      return {-1, -1};

    int l = search_first(nums, target);
    int r = search_last(nums, target);

    bool l_valid = 0 <= l && l <= nums.size() - 1;
    if (l_valid && nums[l] != target) {
      return {-1, -1};
    }

    bool r_valid = 0 <= r && r <= nums.size() - 1;
    if (r_valid && nums[r] != target) {
      return {-1, -1};
    }
    return {l, r};
  }
};

注意要检查返回值是否有效。

这种方法比最后循环找最先 / 最后的第一种方法更好，因为它能以指数速度快速逼近最先 / 最后相同元素。

练习

35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode） (leetcode-cn.com)

275. H 指数 II - 力扣（LeetCode） (leetcode-cn.com)

二叉搜索树

二叉搜索树满足：对于任意节点，其左子及其后代 <= 自身 <= 右子及其后代。

数组转二叉树

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)

我们的思路就是分治。例如对于 {-10, -3, 0, 5, 9}，可以将其划分为 {-10, -3}, {0}, {5, 9}。然后对于两侧，重复这一操作即可。需要注意的就是区间的取舍，避免重漏。

参考解法：


class Solution {
  //from, to 左闭右开，即不含 to
  TreeNode *slice_to_bst(vector<int> &v, int from, int to) {
    if (from == to) {
      return nullptr;
    }
    auto mid = from + (to - from) / 2;
    auto left = slice_to_bst(v, from, mid);
    auto right = slice_to_bst(v, mid + 1, to);
    return new TreeNode(v[mid], left, right);
  }

public:
  TreeNode *sortedArrayToBST(vector<int> &v) {
    return slice_to_bst(v, 0, v.size());
  }
};

我下面的解法性能能提高 250%，不知道什么原因。

#include <debug.h>

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

void print_indent(int n) {
  for (int i = 0; i < n; i++) {
    printf(" ");
  }
}

void print_tree(TreeNode *t, int ind = 0) {
  print_indent(ind);
  if (t == nullptr) {
    printf("NULL\n");
    return;
  }
  printf("%d\n", t->val);
  print_tree(t->left, ind + 2);
  print_tree(t->right, ind + 2);
}

class Solution {
  //from, to 左闭右开，即不含 to
  TreeNode *slice_to_bst(vector<int> &v, int from, int to) {
    if (from == to) {
      return nullptr;
    }
    auto mid = from + (to - from) / 2;
    auto left = slice_to_bst(v, from, mid);
    auto right = slice_to_bst(v, mid + 1, to);
    return new TreeNode(v[mid], left, right);
  }

public:
  TreeNode *sortedArrayToBST(vector<int> &v) {
    auto mid = v.size() / 2;
    auto left = slice_to_bst(v, 0, mid);
    auto right = slice_to_bst(v, mid + 1, v.size());
    return new TreeNode(v[mid], left, right);
  }
};

int main(int argc, char const *argv[]) {
  Solution s;
  vector<int> v = {-10, -3, 0, 5, 9};
  auto t = s.sortedArrayToBST(v);
  print_tree(t);
  return 0;
}

合并排序（归并排序）

合并排序的思想，下面这张图讲得足够清楚了：（来源：图解排序算法 (四) 之归并排序 - dreamcatcher-cx - 博客园 (cnblogs.com)）

可以看到，对于 {8 4 5 7 1 3 6 2}，将其划分为 {{8 4 5 7} {1 3 6 2}} 两个向量。对于每一个再执行相同的操作。也由于这个特点归并排序可以并行计算。

关键在于合并的策略，目测可以采用双指针法，两个指针指向两个向量的头部，然后更小的先入队。即 88. 合并两个有序数组 - 力扣（LeetCode） (leetcode-cn.com) 这题用的方法是尾部插入：

    // v1 = {1, 2, 2, 3, 9，0, 0, 0, 0, 0, 0}
    // v2 = {1, 2, 4, 5, 6, 11}

    // v1 = {1, 2, 2, 3, 9} v2 = {1, 2, 4, 5, 6, 11}
    //                   ^                        ^
    //                   l                        r

    // v1 = {1, 2, 2, 3, 9，0, 0, 0, 0, 0, 11}
    // v1 = {1, 2, 2, 3, 9} v2 = {1, 2, 4, 5, 6, _}
    //                   ^                    ^
    //                   l                    r

    // v1 = {1, 2, 2, 3, _，0, 0, 0, 0, 9, 11}
    // v1 = {1, 2, 2, 3, _} v2 = {1, 2, 4, 5, 6, _}
    //                ^                       ^
    //                l                       r

    // v1 = {1, 2, 2, 3, _，0, 0, 0, 6, 9, 11}
    // v1 = {1, 2, 2, 3, _} v2 = {1, 2, 4, 5, _, _}
    //                ^                    ^
    //                l                    r

    // v1 = {1, 2, 2, 3, _，0, 0, 5, 6, 9, 11}
    // v1 = {1, 2, 2, 3, _} v2 = {1, 2, 4, _, _, _}
    //                ^                 ^
    //                l                 r

    // v1 = {1, 2, 2, 3, _，0, 4, 5, 6, 9, 11}
    // v1 = {1, 2, 2, 3, _} v2 = {1, 2, _, _, _, _}
    //                ^              ^
    //                l              r

    // v1 = {1, 2, 2, _, _，3, 4, 5, 6, 9, 11}
    // v1 = {1, 2, 2, _, _} v2 = {1, 2, _, _, _, _}
    //             ^                 ^
    //             l                 r

    // v1 = {1, 2, _, 2, 2，3, 4, 5, 6, 9, 11}
    // v1 = {1, 2, _, _, _} v2 = {1, _, _, _, _, _}
    //          ^                 ^
    //          l                 r

    // v1 = {1, _, 2, 2, 2，3, 4, 5, 6, 9, 11}
    // v1 = {1, _, _, _, _} v2 = {1, _, _, _, _, _}
    //       ^                    ^
    //       l                    r

    // v1 = {1, 1, 2, 2, 2，3, 4, 5, 6, 9, 11}
    // v1 = {_, _, _, _, _} v2 = {_, _, _, _, _, _}
    //       ^                    ^
    //       l                    r

参考代码：

class Solution {
public:
  // 初始条件下，v1 的长度是 m+n
  void merge(vector<int> &v1, int m, vector<int> &v2, int n) {
    int l = m - 1, r = n - 1, ins = m + n - 1; //ins: 插入位置
    while (l >= 0 && r >= 0) {
      if (v1[l] > v2[r]) {
        v1[ins] = v1[l];
        ins--;
        l--;
      } else {
        v1[ins] = v2[r];
        ins--;
        r--;
      }
    }
    // 注意收尾工作。
    while (r >= 0) {
      v1[ins] = v2[r];
      ins--;
      r--;
    }
  }
};

另外除了从尾部插入，也可以从头部插入，具体方法是：将数组 nums1 的数据往后平移到末尾。留出头部的空间，然后再用双指针指向两个数组有效位置开头，比较谁更小，更小的插入。

参考代码：

class Solution
{
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n)
    {
        for (size_t i = 1; i <= m; i++)
        {
            nums1[m + n - i] = nums1[m - i];
        }
        int p = 0;
        int q = 0;
        int sorted = -1;
        while (true)
        {
            if (p == m && q == n)
            {
                break;
            }

            if (p == m)
            {
                nums1[++sorted] = nums2[q];
                q++;
                continue;
            }

            if (q == n)
            {
                nums1[++sorted] = nums1[n + p];
                p++;
                continue;
            }

            if (nums1[n + p] <= nums2[q])
            {
                nums1[++sorted] = nums1[n + p];
                p++;
            }
            else
            {
                nums1[++sorted] = nums2[q];
                q++;
            }
        }
    }
};

言归正传，我们来实现一下归并排序：

class Solution {
  int *tmp;

public:
  void merge_vec(vector<int> &v, int from, int mid, int to) {
    int l = from, r = mid, ins = 0;
    while (l < mid && r < to) {
      if (v[l] < v[r])
        tmp[ins++] = v[l++];
      else
        tmp[ins++] = v[r++];
    }
    while (l < mid)
      tmp[ins++] = v[l++];

    while (r < to)
      tmp[ins++] = v[r++];

    for (int i = from; i < to; i++)
      v[i] = tmp[i - from];
  }
  void merge_sort(vector<int> &v, int from, int to) {
    if (to - from <= 1)
      return;
    auto mid = from + (to - from) / 2;
    merge_sort(v, from, mid);
    merge_sort(v, mid, to);
    merge_vec(v, from, mid, to);
  }
  vector<int> sortArray(vector<int> &v) {
    tmp = (int *)malloc(v.size() * sizeof(int));
    merge_sort(v, 0, v.size());
    free(tmp);
    return v;
  }
};

详细版：

class Solution {
  // 临时存放排序后的升序元素
  vector<int> tmp;

public:
  void merge_vec(vector<int> &v, int iv1from, int iv1to, int iv2from,
                 int iv2to) {
    // printf("part1 = ");
    // print_vec_part(v, iv1from, iv1to);
    // printf("part2 = ");
    // print_vec_part(v, iv2from, iv2to);

    int l = iv1from, r = iv2from, ins = 0; //ins 表示插入位置
    while (l < iv1to && r < iv2to) {
      // 将较小的复制到 tmp 的开头
      if (v[l] < v[r]) {
        tmp[ins] = v[l];
        l++;
        ins++;
      } else {
        tmp[ins] = v[r];
        r++;
        ins++;
      }
    }
    // 最后有剩余
    while (l < iv1to) {
      tmp[ins] = v[l];
      l++;
      ins++;
    }
    while (r < iv2to) {
      tmp[ins] = v[r];
      r++;
      ins++;
    }
    // 将临时元素覆盖 iv1from, iv2to 的 v 的空间
    for (int i = iv1from; i < iv2to; i++) {
      v[i] = tmp[i - iv1from];
    }
    // printf("merged [%d,%d] = ", iv1from, iv2to - 1);
    // print_vec_part(v, iv1from, iv2to);
  }
  // 左闭右开
  void merge_sort(vector<int> &v, int from, int to) {
    if (to - from <= 1) {
      return;
    }
    auto mid = from + (to - from) / 2;
    // printf("from = %d\n", from);
    // printf("to = %d\n", to);
    // printf("mid = %d\n", mid);
    merge_sort(v, from, mid);
    merge_sort(v, mid, to);
    merge_vec(v, from, mid, mid, to);
  }
  vector<int> sortArray(vector<int> &v) {
    tmp = vector<int>(v.size());
    merge_sort(v, 0, v.size());
    return v;
  }
};

练习

912. 排序数组 - 力扣（LeetCode） (leetcode-cn.com)

正序数组的中位数

这道题被标记为困难，其实考的是数学，只要顿悟，就会觉得非常简单。思路：成对删除。假设有 a=[1,2,5,6,13] b=[3,5,8,12,14,16,18,19]，我们要找中位数，只需要反复删除最大，最小的，直到最后剩下一个或一对元素，其均值就是答案。

[1,2,5,6,13] [3,5,8,12,14,16,18,19]
delete 1,19
[2,5,6,13] [3,5,8,12,14,16,18]
delete 2,18
[5,6,13] [3,5,8,12,14,16]
delete 5,16
[6,13] [3,5,8,12,14]
delete 3,14
[6,13] [5,8,12]
delete 5,13
[6] [8,12]
delete 6,12
med = 8

问题在于这样做删除太慢，你看文字数量的变化也知道是 $O (n)$。优化方案就是批量删除。也很简单，每次删除数量为较短序列长的一半，我不知道为什么别人的题解会写得那样复杂。其实只要一个例子，大家就很容易理解。

来个例子：

a =	1,	6,	15,	19,	26,	33,	42,	46,	56,	58,	63,	64,	68,	78,	80,	89,	97,	99,	99
b =	7,	8,	10,	13,	15,	20,	28,	29,	33,	39,	42,	51,	58,	59,	66,	75,	78,	85,	86

a =	1,	6,	15,	19,	26,	33,	42,	46,	56,	58
b =	39,	42,	51,	58,	59,	66,	75,	78,	85,	86

a =	33,	42,	46,	56,	58
b =	39,	42,	51,	58,	59

a =	46,	56,	58
b =	39,	42,	51

a =	46,	56
b =	42,	51

a =	46
b =	51

med = 48.5

不服？再来！

a	8,	17,	25,	29,	36,	43,	46,	51,	59,	62,	65,	67,	71,	73,	76,	84,	90,	97
b	2,	4,	11,	15,	25,	31,	41,	46,	55,	57,	65,	74,	76,	79,	80,	89

注意到最小值和最大值分属 b, a. 我们选择较短的 b. 长度 16，则从 8 的位置劈开：

2,	4,	11,	15,	25,	31,	41,	46,	<>	55,	57,	65,	74,	76,	79,	80,	89

把小端删除：

<>	55,	57,	65,	74,	76,	79,	80,	89

删除了八个，则同理把 a 中大端删除 8 个。得到：

a	8,	17,	25,	29,	36,	43,	46,	51,	59,	62
b	55,	57,	65,	74,	76,	79,	80,	89

这次我们发现最小值在 a 这边，最大值在 b 这边。由于 b 最短，长度 8，我们一次性只能删除 8/2=4 个，所以从 a 的小端删除 4 个，从 b 的大端删除 4 个。

a	36,	43,	46,	51,	59,	62
b	55,	57,	65,	74

同理操作：

a	46,	51,	59,	62
b	55,	57

此时问题变得有趣起来，a 区间实际上套住了 b 的区间。注意，我们不能因此直接返回 a 的中位数。请继续操作：

a	51,	59
b	55,	57

a	
b	55,	57

好，答案来了，是 56.

为什么呢？原理比较像区间套定理（好吧其实关系不大），只要能保证中位数总是没有被删除，就可以保证最后一定能逼近中位数。

a = {1, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4}
b = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 4}

a = { 4, 4, 4, 4, 4, 4, 4, }
b = { 1, 1, 1, 1, 1, 1, 1, 1, }

哈夫曼树

哈夫曼树是带权路径长度最短的树。

带权路径长度（Weighted path length, WPL）：

路径长度：从根节点到某节点经过的边数。例如上面的 15 节点，其与根节点 100 之间的路径长度是 2.

带权路径长度就是各个叶子节点的权重乘以路径长度最后求和。例如上面：$2 \times 15 + 3 \times 31 + 3 \times 4 + 2 \times 20$

如果改变树的形态，WPL 会随之变化。存在至少一种树的形态，使得 WPL 最小，这种树就是哈夫曼树。

哈夫曼树的特点：权值越大的叶子离根越近。

因此构造哈夫曼树的思想就是将权值小的成树，自下而上构建。（贪心算法）

构造哈夫曼树

数据结构与算法基础 – 第 09 周 03–5.7 哈夫曼树及其应用 3-5.7.2 哈夫曼树的构造算法 1 bilibili

（1）构造一个全为根的森林，数量为权值的数量。记为 $F$。

（2）在 F 中，选择权最小的两个根，将二者作为左右子树，将二者之和作为根权，构造二叉树。

（3）在 F 中，删除这两棵树，用新的二叉树替代。

新的二叉树的根就作为代表元，重复上述操作，直到得到单根树即可。

【例子】从权值 7,5,5,2,4 的节点构造哈夫曼树。

解：构造过程如下

Dijkstra 算法

一种最短路径查找的贪心算法。

【算法】最短路径查找 —Dijkstra 算法_哔哩哔哩_bilibili

【例子】求下面图 0 到 4 节点的最短路径。

历史节点：map<int, bool> visited; 表示节点是否访问过。

出发点距离表：map<int, int> min_dis; 表示节点距离出发点的最短距离。默认是无穷大。

路径表：map<int, int> prev; 表示节点的上一个节点坐标。相当于链表。

Dijkstra 算法的步骤：

筛选出未访问节点列表 int unvisited []。对于每个 u：
1. 找出哪个节点距离出发点最近，即 min_dis [u] 最小值对应的 u
2. 将其标记为访问过 visited [u] = true
筛选出 u 附近的未标记节点 adj_and_unvisited []。对于每个 a：
1. 利用 min_dis [u] + dis [u,a] 得到 A 经过 U 到出发点的距离 try_dis。
2. 如果 try_dis<min_dis [a]，则 min_dis [a] = a，并更新 prev [a] = u