善于利用 查找表 解决查找问题

简介: 善于利用 查找表 解决查找问题

善于利用 查找表 解决查找问题


查找表(Lookup Table)是用简单的查询操作替换运行时计算的数组或者关联数组这样的数据结构。由于从内存中提取数值经常要比复杂的计算速度快很多,所以这样得到的速度提升是很显著的。

说人话,将输入和输出存在表里,这样根据输入能快速查找到输出,而不需要经过复杂的计算。

在算法里,经常会将在数组里的某种操作变成查找表,从而降低时间复杂度:

  • 快速找到数组中某个值的位置:遍历数组,建立 Map,值是键,索引是值,复杂度就从 O(n)变成 O(1)
  • 快速找到数组中某个值出现的次数:遍历数组,建立 Map,值是键,索引是次数,复杂度就从 O(n)变成 O(1)
// 数组中每个元素对应的索引
function getIndexMap(arr) {
  // 兼容字符串的写法
  const map = {};
  for (let i = 0; i <= arr.length; i++) {
    map[arr[i]] = i;
  }
  return map;
}
// 数组中每个元素 出现了几次
function getCountMap(arr) {
  // 兼容字符串的写法
  const map = {};
  for (let i = 0; i <= arr.length; i++) {
    const cur = arr[i];
    map[cur] = map[cur] ? map[cur] + 1 : 1;
  }
  return map;
}

练习 1:两个数组的交集

网络异常,图片无法展示
|

显然是查找一个元素是不是在另一个数组中出现过,而且还关注出现了几次。

于是思路就有了:

  • 将数组 nums1 的元素和次数形成 Map
  • 设置数组变量 res,表示最终的结果
  • 遍历数组 nums2,Map 中有元素的话,且对应的次数是正整数的话,才将元素推进 res 中,然后将对应的次数减去一,这样就能保证 res 中元素出现的是最少次数
var intersect = function (nums1, nums2) {
  // getCountMap就是上面的函数
  const countMap = getCountMap(nums1);
  const res = [];
  nums2.forEach((item) => {
    if (countMap[item]) {
      res.push(item);
      countMap[item] = countMap[item] - 1;
    }
  });
  return res;
};

练习 2:找不同

网络异常,图片无法展示
|

思路是不是极其相似,这里字符串和数组其实是类似的:

  • 将 str1 的元素和次数形成 Map
  • 遍历 str2,Map 中没有元素或者对应的次数是正整数的话,直接返回结果,否则然后将对应的次数减去一
var findTheDifference = function (s, t) {
  // getCountMap就是上面的函数
  const countMap = getCountMap(s);
  for (let i = 0; i < t.length; i++) {
    const cur = t[i];
    if (!countMap[cur]) {
      return cur;
    }
    countMap[cur]--;
  }
};

当然因为只有一个,还有别的鬼法子:

  • s 和 t 中每个字符的 ASCII 码的值求和,两和相减的值转成的字母就是结果
  • s 和 t 合并,然后位运算得到的值就是结果

但是当添加的字母不止一个的时候,还是查找表的法子好使些:

var findTheDifference = function (s, t) {
  // getCountMap就是上面的函数
  const countMap = getCountMap(s);
  let res = "";
  for (let i = 0; i < t.length; i++) {
    const cur = t[i];
    if (!countMap[cur]) {
      res += cur;
    } else {
      countMap[cur]--;
    }
  }
  return res;
};

其实只要频繁用到某种计算结果,就可以使用查找表降低时间复杂度~

引用

目录
相关文章
|
存储 索引
【软考学习15】索引文件结构、直接索引和间接索引
【软考学习15】索引文件结构、直接索引和间接索引
430 0
|
4月前
|
算法
算法—查找假币
算法—查找假币
75 0
|
算法
查找
查找是指在图中寻找特定的节点或边的过程。在图中进行查找操作可以帮助我们找到与目标节点或边相关的信息,或者判断图中是否存在某个节点或边。 在图中进行查找操作的常见算法有: 1. 深度优先搜索(DFS):从图中的一个节点开始,沿着一条路径一直深入直到无法再深入为止,然后回溯到上一个节点,继续深入其他路径,直到找到目标节点或遍历完所有节点。 2. 广度优先搜索(BFS):从图中的一个节点开始,先访问它的所有邻居节点,然后再依次访问邻居的邻居节点,直到找到目标节点或遍历完所有节点。 3. Dijkstra算法:用于在带权有向图中找到从一个节点到其他节点的最短路径。该算法通过不断更新节点的最短距离来逐步
95 0
|
9月前
查找数据
查找数据。
56 1
|
SQL 关系型数据库 MySQL
MySQL索引补充
MySQL索引补充
99 0
|
存储 算法 项目管理
|
算法
数据结构上机实践第14周项目2 - 二叉树排序树中查找的路径
数据结构上机实践第14周项目2 - 二叉树排序树中查找的路径
111 0
数据结构上机实践第14周项目2 - 二叉树排序树中查找的路径
|
算法 大数据 索引
算法查找——分块查找
分块查找是折半查找(二分查找)和顺序查找的一种改进方法,分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。分块查找的速度虽然不如折半查找算法,但比顺序查找算法快得多,同时又不需要对全部节点进行排序
285 0
算法查找——分块查找
|
存储 自然语言处理 算法
数据结构与算法分析学习笔记(七) 索引与查找技术
数据结构与算法分析学习笔记(七) 索引与查找技术
数据结构与算法分析学习笔记(七) 索引与查找技术
|
存储 算法 Java
练习2—数据查找
练习2—数据查找
108 0