查找字符串中字符之间的长度

我有一个从字符和字符串到整数数组的函数。该数组的索引是字符在文本中出现的次数，该索引的条目是与文本中显示的前一个字符的距离。如果该字符是换行符，则该函数基本上计算给定字符串的行长度数组。查找字符串中字符之间的长度

val func: Char => (String => Array[Int]) = (ch: Char) => (str: String) => { 
    var lens: Array[Int] = new Array[Int](20) 
    var noCh: Int = 0 
    var c: Int = 0 // accumlates till the next character is spotted 
    for (i <- 0 until str.length) { 
     c += 1 
     if (str.charAt(i) == ch) { 
      if (noCh>= lens.length) { 
       val newlen: Array[Int] = new Array[Int](2*noCh) 
       Array.copy(lens,0,newlen,0,noCh) 
       lens = newlen 
      } 
      lens(noCh) = c; c = 0; noCh+= 1 
     } 
    } 
    lens 
    }           //> func : Char => (String => Array[Int]) = <function1> 
    func('\n')("hello world \n hello wstsadfasdf \n sdlfkjasdf\n") 
                //> res2: Array[Int] = Array(13, 20, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
                //| 0, 0, 0, 0)

有没有更快的方法来解决这个问题？迭代每个角色似乎非常缓慢，特别是如果你经历一个非常大的字符串。

来源

2016-01-15 user2850249

请举几个例子：'f（x）=== y'其中'f'是你所要求的函数，''x'是你的输入，'y'是预期的输出。假设我想要一个将数字加2的函数，我会写：'f（1）=== 3'，'f（0）=== 2'等等。 –

O（N）运行时对于扫描一个字符串是微不足道的，并且永远不会更快，除非您一次对字符串预先扫描一个字符到一个哈希映射中，并且您只是一次又一次地使用同一个字符串。但是，分配数组并最终返回一个填满零的数组可能是浪费时间，但肯定是结果错误。如果你真的必须有一个数组，你可以构建一个List [Int]或Seq [Int]并将其转换为完美结果大小的Array [Int]。 – LaloInDublin

如果ch不是字符串中的最后一个字符，结果如何？ –

正如其他人所说，需要扫描字符串。你还有什么可以找到ch的事件？但你肯定做的是恶劣天气，因为它是一个班轮：

def func(ch:Char)(str:String):Array[Int] = 
str.foldLeft(List(1)){(a,c)=>if(c!=ch) a.head+1::a.tail else 1::a}.tail.reverse.toArray 

func('\n')("hello world \n hello wstsadfasdf \n sdlfkjasdf\n") 
//> res0: Array[Int] = Array(13, 20, 12)

或（更简单，虽然可能有点不太有效，因为它会创建一个字符串数组）

def func2(ch:Char)(str:String):Array[Int] = str.split(ch).map(_.length+1)

来源

2016-01-15 09:12:46

嗯，好的，谢谢代码的改进。扫描字符串的方法仍然基本相同，这是我想要改进的地方（但似乎这只是解决方案） – user2850249

通过字符串进行线性扫描，您无法做任何事情。这很明显，你需要检查每个字符，看看它是否是“ch”...... –

该方法将如何工作？通过魔法预测下一个角色的位置？您可以构建有序集合的Map来加速查询。不过，建造时间仍然是O(n)。但是查询可以在O(1)中执行。

来源

2016-01-15 01:35:27 Paul

查找字符串中字符之间的长度

回答

相关问题