一个数组,大小和每个元素的值在编译时已知。设计一个算法用最快速的方式计算两个下标间所有数组元素的和
小弟想了下int beginIndex;
int endIndex;
for(int i=beginIndex;i<=endIndex;i++){
sum+=a[i];
}时间复杂度是O(length)最坏的情况是0 - array.length
不会就这么简单吧?求各位给看看,小弟感激不敬
小弟想了下int beginIndex;
int endIndex;
for(int i=beginIndex;i<=endIndex;i++){
sum+=a[i];
}时间复杂度是O(length)最坏的情况是0 - array.length
不会就这么简单吧?求各位给看看,小弟感激不敬
解决方案 »
- JAVA io 读写速度方面的问题 为啥笔记本比服务器快一倍
- 关于无符号右移的问题 int a = -4321 >>>32;
- 帮我解决了换行的问题!谢谢大家!
- 如何在java api文档中迅速找到某个方法
- 在线帮小弟一个忙,如何用java实现开发工具中的智能提示
- 急问:eclipse3.2里开发的SWT程序怎么生成能部署的jar
- 如何在jar包中调用exe等资源文件
- 我是一个菜鸟,请问是c语言好学还是java好学?
- 高难问题:applet里面如何取得session?因为要对applet的操作进行控制
- abstract class 的构造函数问题!!!(急)
- 遍历字符串,并依次查看每个代码点
- 求教CXF怎么发布返回值是抽象类的方法?
int [] b = new int[a.length];
for (int i=0; i<a.length; i++)
b[i] = i == 0 ? 0 : b[i-1] + a[i];public int getSum(beginIndex, endIndex) {
return b[endIndex] - beginIndex == 0 ? 0 : b[beginIndex - 1];
}
我把你的代码改了下作了下调试你看是这样的不?
/* 程序初始化时,重新定义一个数组,数组的元素是目标数组中每个元素到目标数组开始位置的所有元素的和
例如b[2]=a[0]+a[1]+a[2]
*/
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++)
b[i] = i == 0 ? a[0] : b[i - 1] + a[i];
/**
* 题目二:一个数组,大小和每个元素的值在编译时已知
* 设计一个算法用最快速的方式计算两个下标间所有数组元素的和。
* @param a 被计算的数组
* @param beginIndex 数组被计算和的开始位置下标
* @param endIndex 数组被计算和的结束位置下标
* @return 下标间所有数组元素的和
* @throws Exception 下标值不满足要求时抛出异常
*/
public int getSum(int beginIndex, int endIndex) throws Exception {
if (endIndex > a.length -1) {
throw new IndexOutOfBoundsException("结束下标超过数组长度");
}
if (beginIndex < 0) {
throw new IndexOutOfBoundsException("开始下标小于0");
}
if ((endIndex - beginIndex < 0)) {
throw new Exception("被计算的结束下标需要比开始下标大");
}
return endIndex - beginIndex == 0 ? 0 : b[endIndex]- b[beginIndex]+ a[beginIndex];
}