分裂字符串没有string.Split

我正在做一个家庭工作问题，不使用框架方法拆分字符串。

以下是我提出的工作代码。

我想知道如何改善O（n）的运行时间？

此外，欢迎任何改进建议。

public static string[] split(string txt, char[] delim) { char[] text = txt.ToCharArray(); string[] result = new string[0]; int count = 0; int i = 0; StringBuilder buff = new StringBuilder(); while(i < text.Length) { bool found = false; foreach(char del in delim) { if(del == txt[i]) { found = true; break; } } if(found) { count++; Array.Resize(ref result, count); result[count - 1] = buff.ToString(); buff = new StringBuilder(); } else { buff.Append(txt[i]); } i++; } if(buff.Length != 0) { count++; Array.Resize(ref result, count); result[count - 1] = buff.ToString(); } return(result); } 

Answer 1

我有一些更改会同时使这个函数更像C，并将运行时间减少到O（n）：

1）你应该用很多次创建它来保存最大数量的字符串（你知道这个数字小于txt.Length ），然后在最后一次调整它的大小，而不是动态调整result数组的大小。归还它。

2）不要使用StringBuilder组合你的结果，而是制作一个长度为txt.Length的char[] buff和一个索引变量j并执行buff[j++] = txt[i] 。

我认为你的function应该是O（N）。 从技术上讲，它将是O（N * M），其中M是分隔符的数量。

编辑1：

这是一个改变，它将使O（N）+ O（M）而不是O（N * M）：

您应该循环遍历ADVANCE中的分隔符并设置如下数组，而不是循环遍历字符串中每个字符的分隔符：

 bool[] isDelimiter = new bool[128]; // increase size if you are allowing non-ascii foreach(char delim in isDelimiter) { isDelimiter[(int)char] = true; } 

然后你可以使用这个数组在恒定时间内测试字符串的每个字符。

Answer 2

我认为你的教授正在寻找一种只需要一个字符的API，而不是一个数组。 不是一个字符数组。 我的意思是，如果你的分隔字符串是“abcd”，你就不会分裂’a’，’b’，’c’，’d’的所有实例。 如果找到整个字符串，则只会拆分。

您当前的算法不是O（n），因为对于输入数组中的每个元素，您将它与分隔数组的每个元素进行比较。 这导致O（n * m）执行时间。

我认为不可能将其转换为O（n），因为输入上的每个元素都需要与分隔符数组的每个元素进行比较。 我认为你的教授可能更有可能就分隔符数组提出一个不同的问题。

 public static String[] Split(String input, String delimiter) { List parts = new List(); StringBuilder buff = new StringBuilder(); if (delimiter.Length > 1) //you are splitting on a string not a character { //perform string searching algorithm here } else if(delimiter.Length == 0) { throw new InvalidOperationException("Invalid delimiter."); } else //you are splitting on a character { char delimChar = delimiter[0]; for (int i = 0; i < input.Length; i++) { if (input[i] == delimChar) { parts.Add(buff.ToString()); buff.Clear(); } else { buff.Append(input[i]); } } } return parts.ToArray(); } 

C＃的String.Split()确实接受了一个分隔符数组，但我不相信它会在O（n）时间内进行分割。

如果您正在研究字符串搜索算法，这些可能会有所帮助。 http://en.wikipedia.org/wiki/String_searching_algorithm

编辑：我错误地提到了C＃的String.Split() API没有采用分隔符数组这一事实。

Answer 3

如果将分隔符放入HashSet，则可以将其设为O（n）。 测试HashSet中是否存在值是O（1）。

 var delimterSet = new HashSet(delim); 

…

 if(delimterSet.Contains(txt[i]) { ... } 

但是，对于少数分隔符，这不会改善性能。

Answer 4

由于必须遍历/搜索分隔符列表，因此无法在O（n）中执行String.Split。

Answer 5

也许你可以尝试一次完成所有的工作

 public static String[] Split(String txt, char[] delim) { if (txt == null) return new String[0]; // or exception if (delim == null || delim.Length == 0) return new String[0]; // or exception char[] text = txt.ToCharArray(); string[] result = new string[1]; // If there is no delimiter in the string, return the whole string int part = 0; int itemInArray = 1; for (int i = 0; i < text.Length; i++) { if (IsIn(delim, text[i])) { Array.Resize(ref result, ++itemInArray); // Is it consider as a framework method ??? part++; } else result[part] += text[i]; } return result; } public static Boolean IsIn(char[] delim, char c) { for (int i = 0; i < delim.Length; i++) if (c == delim[i]) return true; return false; }