首页 > 试题广场 >

n100）个段落，第i个段落有number[i]个单词，

[问答题]

<n><100）个段落，第i个段落有number[i]个单词，设计算法，不得调用库函数，找出第m个单词属于第几个段落，查询共有k（k>一篇文章有n（10<n<100）个段落，第i个段落有number[i]个单词，设计算法，不得调用库函数，找出第m个单词属于第几个段落，查询共有k（k>10000）次，说明时间复杂度。（段落编号从0开始）

</n>

查看答案及解析

小牧魔法袋

1.定义一个线性表，下标是单词个数，内容是该单词所属的段落，这样直接查询线性表第m位置的内容，时间复杂度为O(1)，不过单词数多耗费空间大。或者用二分查找，定义一个数组，下标为段落，内容为该段落以及之前段落所有单词数量总和，时间复杂度O（log2n）,空间占用低。

2.List<Integer> wordToPara = new ArrayList<Integer>();
int p = 0;
for(int i=0;i<n;i++) {
for(int j=0;j<number[i];j++) {
wordToPara[p] = i;
p++;
}
}
int whichWord = scanner.nextInt();
System.out.println(wordToPara.get(whichWord));

预处理：时间复杂度：单词总个数
查询：时间复杂度： O(1)
空间复杂度：单词总个数。

发表于 2017-11-26 18:41:19 回复(0)