时间复杂性Java

Question

程序计算给定文本时句子中的最大字数。一篇文章可以有多个句子。我必须找到单词最多的句子

我有以下代码，我需要为此优化时间复杂性不应超过5秒

import java.util.*;
import java.io.*;

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        List<Integer> wca=new ArrayList<Integer>();
        int wc,i;
        String[] sent=S.split("\.+");
        while(sent.length!=0){
            for(i=0;i<sent.length;i++){
               wc=sent[i].split("\s+").length; 
               wca.add(wc);
            }
        }
        Collections.sort(wca);
        return(wca.get(wca.size()-1));

    }
}

Answer 1

您不需要对列表进行排序，只需找到其最大值。事实上，你根本不需要一份清单。只需边读边储存最长的句子。

public int findLongestSentence(String paragraph) {
    String[] sentences = paragraph.split("\.|\!|\?");
    int maxSentenceLength = 0;
    for(String sentence : sentences) {
        String[] words = sentence.split("\s");
        maxSentenceLength = Math.max(words.length, maxSentenceLength);
    }
    return maxSentenceLength;
}

这可以通过不使用split()方法来提高效率，但这不会影响渐近时间复杂性。

附言：信息性的变量名很重要，再加上良好的代码格式，使代码更容易阅读。

Answer 2

该程序统计一句话中的最大字数

假设你有这样的文本：

Lorem ipsum dolor坐amet，consectetur adipisci elit，sed eiusmod tempor incident ut labore et dolore magna aliqua。乌特尼姆和最小的威尼斯人，诺斯特鲁德·埃克劳姆科的工作人员是尼西，而不是像康奎特商品一样。这是一个很好的例子。除非你没有得到任何帮助，否则你不应该受到惩罚。

按点拆分（.）

arr[0]= Lorem ipsum dolor sit amet, consectetur adipisici elit, sed eiusmod tempor incidunt ut labore et dolore magna aliqua
arr[1]= Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquid ex ea commodi consequat
arr[2]= Quis aute iure reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur
arr[3]= Excepteur sint obcaecat cupiditat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

单词的数量与空格的数量有关，所以计算空格会更容易

int max=0；//这保持了最大空间计数int索引=0；//这保存了最大空间计数的索引

在数组上迭代

   int spaces = arr[i].length - arr[i].replace(" ","").length;
    if(spaces>max){
         max = spaces;
         index = i;
    }

在循环结束时，您将获得该句子的最大单词量和数组索引

Answer 3

根据我的理解，您想要解析输入文本，这样您就可以获得每个句子的字数，并找到最高的句子。

首先，你只返回最高字数，而没有返回任何内容来识别句子本身。

第二（正如其他人已经指出的）排序可以用只保留最长的句子来代替，当找到一个更长的句子时，替换它。这确实会使它变成O（n）。

第三个问题是句子不能只以句号结尾。

  String longest;
for (String s : sentences){
 if(s.split(" ").length>longest.split(" ").length))
{
longest = s
}
}
return longest;