算法-计算小数组在大数组中的索引

算法,大前端 2018-09-27

前言

大数组:[1,2,3,4,5,6]

小数组:[4,5]

我们需要快速得到小数组在大数组中的索引位置,本例中结果是3

算法思路

1. 暴力,嵌套for循环

function match(arr1,arr2){
  var n = arr1.length
  var m = arr2.length
  f1:
  for(var i=0;i<n;i++){
    if(arr1[i]===arr2[0]){
      f2:
      for(var j=1;j<m;j++){
        if(arr1[i+j]!==arr2[j])continue f1;
      }
      return i
    }
  }
  return -1
}

2. 将数组元素转成字符串,用特殊字符分割

[1,11,3,4,5,6].join('#')="1#11#3#4#5#6"
[4,5].join('#')="4#5"

然后利用字符串匹配算法就可以算得,根据匹配字符前面的#的在源串中是第几个#来得到

问题:

  1. 引入了分割字符后,搜索长度变大,算法耗时变高
  2. 当数组中元素也含有字符串时,就需要辨别1和"1"
  3. 当数组中元素含有字符串时,所选的特殊字符不能处于字符串的字符集中

问题2 我们可以采用JSON格式,就可以识别数字和字符串等基本类型了。

譬如:JSON.stringify([1,'1','3']) 得到 [1,"1","3"] ,我们去除左右两侧中括号得到1,"1","3"

在遍历的时候,我们需要识别分割符,和数组元素为字符串且里面还有,的情况,这样就可以解决问题3。但是这样将限定很多字符串匹配算法,同时还引入问题4

问题 4:大数组中某个元素为字符串,且内容为小数组格式化的结果,导致查询错误

即 大数组:[1,'1,"1","3"','3'],小数组:[1,"1","3"],正常应该不能匹配,但这里按字符串匹配算法的话会导致匹配。

因此还是需要用字符集中没出现的字符做分隔符。需要一个O(n)的预处理时间,此外问题1还是不能解决。

PS:最后算法复杂度为O(n),那问题1就影响不大了。

3. 借鉴 Rabin-Karp 算法思想

具体算法可以参考《字符串匹配算法介绍及js字符串indexOf源码探究》

我们需要把小数组中的元素映射到某个数值,为了快速计算,我们定义以下规则:

number类型:取值=原值%100,将值控制在0~99之间

string类型:取值=第一个字符的ascii码*字符串长度%100+100,将值控制在100~199之间

故字符集长度M为200,我们设哈希表长度Q为 10007

我们写出以下代码:

var Q = 10007
var M = 200
function getValue(item){
  if(typeof item === "number"){
    return item%100
  } else if(typeof item === "string"){
    return item.length>0?item.charCodeAt(0)*item.length%100+100:100
  } else return 0
}
function getHash(arr,len){
  var val = 0
  for(var i=0;i<len;i++){
    val=(val*M+getValue(arr[i]))%Q
  }
  return val
}
//逐个比较相同长度的数组,arr1从index位置开始取
function compare(arr1,arr2,offset){
  for(var i=0;i<arr2.length;i++){
    if(arr1[i+offset]!==arr2[i])return false
  }
  return true
}
function match(arr1,arr2){
  var n = arr1.length
  var m = arr2.length
  if(n<m)return -1
  var arr2Hash = getHash(arr2,m)
  // 一个固定值
  var fix = Q-M**(m-1)%Q
  var curHash = getHash(arr1,m)
  if(curHash===arr2Hash&&compare(arr1,arr2,0))return 0
  for(var i=m;i<arr1.length;i++){
    var offset = i-m+1
    curHash = (((curHash+getValue(arr1[i-m])*fix%Q)*M)+getValue(arr1[i]))%Q
    if(curHash===arr2Hash&&compare(arr1,arr2,offset))return offset
  }
  return -1
}
//match([1,2,3,'1',2,'3'],['1',2]) = 3

实际测试,该算法效率并不高,在于getValue需要做的操作太多了

4. 借鉴KMP的思想

具体算法可以参考《字符串匹配算法介绍及js字符串indexOf源码探究》

举例:

大数组:[1,2,3,4,1,2,'3',1,2,'3',1,2,3,4]

小数组:[1,2,'3',1,2,3]

我们先进行小数组中部分匹配值的计算:

对于字符串abcabd,按以下分析

  • [1] 前缀:[] 后缀:[],最长的共有长度为0
  • [1,2] 前缀:[[1]] 后缀:[[2]],最长的共有长度为0
  • [1,2,'3'] 前缀:[[1],[1,2]] 后缀:[[2,'3'],['3']],最长的共有长度为0
  • [1,2,'3',1] 前缀:[[1],[1,2],[1,2,'3']] 后缀:[[2,'3',1],['3',1],[1]],共有元素为[1],最长的共有长度为1
  • [1,2,'3',1,2] 前缀:[[1],[1,2],[1,2,'3'],[1,2,'3',1]] 后缀:[[2,'3',1,2],['3',1,2],[1,2],[2]],共有元素为[1,2],最长的共有长度为2
  • [1,2,'3',1,2,3] 前缀:[[1],[1,2],[1,2,'3'],[1,2,'3',1],[1,2,'3',1,2]] 后缀:[[2,'3',1,2,3],['3',1,2,3],[1,2,3],[2,3]],最长的共有长度为0

可以得到部分匹配表:

1 2 '3' 1 2 3
0 0  0  1 2 0 

代码如下:

function computeOverlay(pattern){
  var overlay = []
  var k = 0
  overlay[0]=0
  for(var i=1;i<pattern.length;i++){
      k = overlay[i-1]
    if(pattern[k]===pattern[i]){
      overlay[i]=k+1
    } else{
      while(k>0&&pattern[k]!==pattern[i]){
        k = overlay[k-1]
      }
      overlay[i]=k
    }
  }
  return overlay
}
function match(arr1,arr2){
  var n = arr1.length
  var m = arr2.length
  if(n<m)return -1
  var overlay = computeOverlay(arr2)
  f1:
  for(var i=0;i<n;){
    f2:
    for(var j=0;j<m;j++){
      if(arr1[i+j]!==arr2[j]){
        if(j>0&&overlay[j-1]>0){
          //可跳跃时,移动位数 = 已匹配的字符数 - 已匹配最后一个字符其对应的部分匹配值
          i+=j-1-overlay[j-1]
        } else{
          i++
        }
        continue f1;
      }
    }
    return i
  }
  return -1
}

本文由 GaHingZ 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

赏个馒头吧