|
锁定老帖子 主题：一道JAVA面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (2)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-10-21
tq02ksu 写道 我想到一个更简单一点的方法.
启发就是比较连续2组数的时候只需要比较有差别的那2个. 比如: 数据下标 0 1 2 和 1 2 3 比较的时候只需要比较 下标0 和下标3 的大小即可. 这样比较的次数是原来的1/3. 具体实现如下:
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 2, 5, -6, 12, 7, 15, 6, -10, 38 };
Test.find(arr);
}
public static void find(int[] data) {
/**
* make sure the length of data more than or equal 5;
*/
if (data.length <= 5)
return;
/**
* difference between current comparing data subscript
* and max subscript of data
*/
int diff = 0;
/**
* index of max subscript of data, can also be
* a array to record max combinations.
*/
int maxIdx = 0;
for (int i = 1; i < data.length - 2; i++) {
int bigger = data[i - 1] - data[i + 2];
if (diff + bigger > 0) {
diff += bigger;
} else {
maxIdx = i;
diff = data[i - 1] - data[i + 2];
}
}
System.out.println("maxIndex : " + maxIdx + ", data : " + data[maxIdx]
+ ", " + data[maxIdx + 1] + ", " + data[maxIdx + 2] + ". ");
}
}
benchmark了一下. 确实要比楼上的那个实现快一点. 100000次. 这个是1515ms, 楼上的实现是2406ms. 不过还没有达到3倍的效果... 经测试。效率和楼上一样。 |
| 返回顶楼 | |
|
发表时间：2010-10-21
public static void main(String[] args)
{ int[] num = new int[] { 2, 5, -6, 12, 7, 15, 6, -10 }; int length = num.length; ArrayList newArray = new ArrayList(); int i = 0; for (; i < length - 2; i++) { newArray.add(num[i] + num[i + 1] + num[i + 2]); } int max = (Integer) Collections.max(newArray); int index = newArray.indexOf(max); System.out.println(max + "=" + num[index] + "+" + num[index + 1] + "+" + num[index + 2]); } |
| 返回顶楼 | |
|
发表时间：2010-10-22
marshaldong 写道 public static void main(String[] args)
{ int[] num = new int[] { 2, 5, -6, 12, 7, 15, 6, -10 }; int length = num.length; ArrayList newArray = new ArrayList(); int i = 0; for (; i < length - 2; i++) { newArray.add(num[i] + num[i + 1] + num[i + 2]); } int max = (Integer) Collections.max(newArray); int index = newArray.indexOf(max); System.out.println(max + "=" + num[index] + "+" + num[index + 1] + "+" + num[index + 2]); } 这位兄弟对JAVA的基类很精通啊，这个方法最简单了，估计代码量最少 |
| 返回顶楼 | |
|
发表时间：2010-10-22
我怎么看不懂题目的意思啊 、？ 什么叫累加啊？ 累加后怎么办。。。。
|
| 返回顶楼 | |
|
发表时间：2010-10-22
lxs575208196 写道 我怎么看不懂题目的意思啊 、？ 什么叫累加啊？ 累加后怎么办。。。。
累加后形成一个新的数组，然后找出新数组的最大值，然后得到下标，算出新数组是原始数组中哪三个值计算出来的 |
| 返回顶楼 | |
|
发表时间：2010-10-22
public class Lianxi1
{
public static void main(String[]args)
{
int[] sample = {2,5,-6,12,7,15,6,-10};
int[] sample1= {15,8,12,13,5,17};
result(sample1);
result(sample);
}
public static void result(int[] old)
{
int index[]=new int[5];
int max = 0;
int j = 0;
for(int i = 0; i<old.length-2; i++)
{
if(old[i]+old[i+1]+old[i+2]>max)
{
max = old[i]+old[i+1]+old[i+2];
index[j] = i;
}else if(old[i]+old[i+1]+old[i+2]==max)
{
j++;
index[j] = i;
}
}
System.out.println("max="+max);
for(int k = 0;k<=j;k++)
System.out.println(old[index[k]]+","+old[index[k]+1]+","+old[index[k]+2]);
}
}
sample1= {15,8,12,13,5,17}; 这种情况两组都打印 |
| 返回顶楼 | |
