寻找一种算法来查找给定字符串中最长的空白序列的长度,检查尽可能少的字符？
提示:随着空白序列的长度增加,您的程序应该变得更快.
我知道解决方案是O(n)..但寻找更优化的解决方案
您将无法找到比O(n)更小的复杂度的解决方案,因为您需要在最坏情况下使用最多具有0或1个连续空格的输入字符串来传递每个字符,或者完全是空格.
你可以做一些优化,但它仍然被认为是O(n).
例如:
当你浏览列表时,让M成为当前最长的匹配.还假设您可以访问O(1)中的输入元素,例如您有一个数组作为输入.
当您看到非空格时,如果current + M非空格,则可以跳过M个元素.当然没有比M更长的空白.
当你看到一个whitepsace角色时,如果current + M-1不是空白,你知道你没有最长的跑步,你也可以跳过这种情况.
但在最坏的情况下(当所有字符都是空白时),你必须检查每个字符.所以它在复杂性方面不能比O(n)更好.
基本原理:假设整个字符串为空,您没有检查N个字符和算法输出n.然后,如果任何未检查的字符不是空白,您的答案将是错误的.因此,对于此特定输入,您必须检查整个字符串.