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

前言

大数组：[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 需要做的操作太多了