如何改进此O(n ^ 2)字符串处理解决方案? [英] How to improve this O(n^2) string manipulation solution?
问题描述
编写一个函数，该函数接受字符串的输入并返回元组的计数. 格式为(x，y)的元组，其中 x 是'a'的索引， y 是'b'和的索引x ＜ y .
Write a function that takes in an input of a string and returns the count of tuples. Tuples in the form (x,y) where x is index of 'a', y is index of 'b' and x < y.
示例:对于"aab"，答案是两个 对于"ababab"，答案是六个
Examples: For "aab" the answer is two For "ababab" the answer is six
只需在每个"a"之后查找b的个数即可在O(n ^ 2)中完成，但我不确定如何在O(n)中进行. 我试过用2个指针遍历字符串，但是我一直缺少一些元组.我不确定是否可以在O(n)时间内完成.
It can be done in O(n^2) by simply looking for the number of b's after each 'a' but I am not sure how to do it in O(n). I've tried traversing the string with 2 pointers but I keep missing some tuples. I am not sure if this can be done in O(n) time.
推荐答案
此问题是反转计数"问题的特例.通常，问题出在 O(nLog(n))中.可以使用不同的方法来解决:
This problem is a special case of Inversion Count problem. In general the problem is in O(nLog(n)). It can be solved using different methods:
- Using merge sort
- Using Binary Search Tree
- Using a sorted list
- Using Binary Indexed Tree
但是在这种特殊情况下，当您只有两种类型的元素时，可以在 O(n)中完成，如其他答案所解释.只需记住遍历字符串并在遇到b时将它们加在一起的次数即可.
But in this special case when you only have two types of elements it can be done in O(n) as other answers explain. Just remember the number of occurrences of a as you traverse the string and sum them together when you encounter a b.
这篇关于如何改进此O(n ^ 2)字符串处理解决方案?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
