超复杂算法，如何求得数组中的绝对值的最大值

给出一个以0为起始索引的非空数组 A 其中包含 N 个非负整数，返回数组 A 中任意两个元素之差的绝对值的最大值:

amplitude(A) = max{ A[P] − A[Q] : 0 ≤ P, Q < N }

编写一个函数

class Solution { public int amplitude(int[] A); }

假定:

N 是 [1..1,000,000] 内的 整数;

数组 A 每个元素是取值范围 [0..5,000,000] 内的 整数 .

例如，给出

 A[0] = 10  A[1] = 2   A[2] = 44

 A[3] = 15  A[4] = 39  A[5] = 20

你的函数应该返回 42.

复杂度:

最坏-情况下，期望的时间复杂度是 O(N);

最坏-情况下，期望的空间复杂度是 O(1), 输入存储除外 (不计输入参数所需的存储空间).

输入数组中的元素可以修改.

评论

24 楼 抛出异常的爱 2013-03-11  

kidneyball 写道

duoduodeai 写道

JianbinJava 写道

楼猪,,你要讲的是排序还是求最大值..
标题跟内容不相符啊...

傻帽，看不懂吗？老师先给你分析下题目，首先求求组中所有相邻元素的值差，然后求绝对值，最后求绝对值中的最大值，傻帽，回家练练吧，这里不适合你。

楼主原帖中完全没有提到“相邻”，2楼不知怎么的就按着“相邻”来做，真是很离奇。题目要求时间复杂度O(N)，时间复杂度是按元素访问来算的，2楼的解法在一个双层循环里Math.abs(a[i] - a[i + 1])，时间复杂度怎么看也不象是O(N)吧。

max = 0 ;
index_max = 0;
for(i=0 ; i < a.langth-1 ;i++){
   if(max < abs(a[i]-a[i+1])){
       max = a[i] -a[i+1];
       index_max = i ;
    }

}
sysout(max);
sysout(index_max);

o(n)
o(1)

相邻?

23 楼 shenliuyang 2013-03-11  

给一堆数， 求出任意两个数相减后。 求他们的绝对值的最大值。

22 楼 ahack 2013-03-11  

kidneyball 写道

duoduodeai 写道

JianbinJava 写道

楼猪,,你要讲的是排序还是求最大值..
标题跟内容不相符啊...

傻帽，看不懂吗？老师先给你分析下题目，首先求求组中所有相邻元素的值差，然后求绝对值，最后求绝对值中的最大值，傻帽，回家练练吧，这里不适合你。

楼主原帖中完全没有提到“相邻”，2楼不知怎么的就按着“相邻”来做，真是很离奇。题目要求时间复杂度O(N)，时间复杂度是按元素访问来算的，2楼的解法在一个双层循环里Math.abs(a[i] - a[i + 1])，时间复杂度怎么看也不象是O(N)吧。

看到这种2B楼主真心蛋疼。

21 楼 kidneyball 2013-03-11  

duoduodeai 写道

JianbinJava 写道

楼猪,,你要讲的是排序还是求最大值..
标题跟内容不相符啊...

傻帽，看不懂吗？老师先给你分析下题目，首先求求组中所有相邻元素的值差，然后求绝对值，最后求绝对值中的最大值，傻帽，回家练练吧，这里不适合你。

楼主原帖中完全没有提到“相邻”，2楼不知怎么的就按着“相邻”来做，真是很离奇。题目要求时间复杂度O(N)，时间复杂度是按元素访问来算的，2楼的解法在一个双层循环里Math.abs(a[i] - a[i + 1])，时间复杂度怎么看也不象是O(N)吧。

20 楼 shenliuyang 2013-03-11  

看了标题来的， 猛的一看详情，  尼玛 小学 题目。

19 楼 albrich 2013-03-11  

youtops 写道

怎么这么多人排序，直接一次遍历找到最大值最小值就可以了
amplitude(A) = max{ A[P] − A[Q] : 0 ≤ P, Q < N }
amplitude(A) = =max{A[i],0 ≤ i}-min{A[j],0 ≤ j}

就是找到集合A中的最大值-A中的最小值

伪代码如下：
int max = A[0];//记录当前遍历的最大值 A[0]将修改用来存放最小值
for( int index = 1; index < A.length; index ++)
{
    //max 不是最大，则重新赋值
    if(max < A[index])
    {
        max = A[index];
    }
    // A[0] 不是最小，则重新赋值
    if(A[0] > A[index])
    {
        A[0]  =  A[index];
    }
}
//返回最大值-最小值
return max - A[0];

算法复杂度为O(N) 空间复杂度为O(1)

赞同

18 楼 youtops 2013-03-10  

怎么这么多人排序，直接一次遍历找到最大值最小值就可以了
amplitude(A) = max{ A[P] − A[Q] : 0 ≤ P, Q < N }
amplitude(A) = =max{A[i],0 ≤ i}-min{A[j],0 ≤ j}

就是找到集合A中的最大值-A中的最小值

伪代码如下：
int max = A[0];//记录当前遍历的最大值 A[0]将修改用来存放最小值
for( int index = 1; index < A.length; index ++)
{
    //max 不是最大，则重新赋值
    if(max < A[index])
    {
        max = A[index];
    }
    // A[0] 不是最小，则重新赋值
    if(A[0] > A[index])
    {
        A[0]  =  A[index];
    }
}
//返回最大值-最小值
return max - A[0];

算法复杂度为O(N) 空间复杂度为O(1)

17 楼 李立召 2013-03-10  

使用TreeSet进行了实现：
public class Solution {
public static void amplitude(int[] as) {
Set<Integer> sets = new TreeSet<Integer>();
for (Integer s : as) {
sets.add(s);
}

Integer[] b = new Integer[sets.size()];
sets.toArray(b);
System.out.println(Math.abs(b[0] - b[b.length - 1]));

}

public static void main(String[] args) {
amplitude(new int[] { 10, 2, 44, 15, 39, 20 });
}
}

16 楼 laogao3232 2013-03-10  

遍历数组，算差值，取绝对值。
放入TreeSet，去头尾就是最大与最小值了。

15 楼 duoduodeai 2013-03-10  

JianbinJava 写道

楼猪,,你要讲的是排序还是求最大值..
标题跟内容不相符啊...

傻帽，看不懂吗？老师先给你分析下题目，首先求求组中所有相邻元素的值差，然后求绝对值，最后求绝对值中的最大值，傻帽，回家练练吧，这里不适合你。

14 楼 JianbinJava 2013-03-10  

楼猪,,你要讲的是排序还是求最大值..
标题跟内容不相符啊...

13 楼 duoduodeai 2013-03-10  

hardPass 写道

o(1)?说笑吧。这种需求怎么着都得遍历到吧？
只是遍历一次，记录下最大值和最小值，就可以了么

那个被楼主认为是很好的算法，我没仔细看，只是看到sort，就凌乱了～

怎么会凌乱了呢

12 楼 hardPass 2013-03-10  

o(1)?说笑吧。这种需求怎么着都得遍历到吧？
只是遍历一次，记录下最大值和最小值，就可以了么

那个被楼主认为是很好的算法，我没仔细看，只是看到sort，就凌乱了～

11 楼 lection.yu 2013-03-09  

抛出异常的爱 写道

duoduodeai 写道

gaopenghigh 写道

都是非负整数，那不就是最大值减去最小值吗？  

不是，gao_xianglong已经给出算法了，也谢谢你的回复，小弟谢过了

不是最大减最小的测试用例？

没错。。。。我傻了。还统计四个变量。。最大减最小足以。。遍历一次足矣。。复杂2n

10 楼 lection.yu 2013-03-09  

没错。。。。我傻了。还统计四个变量。。最大减最小足以。。遍历一次足矣。。复杂2n

9 楼 lection.yu 2013-03-09  

遍历一次，分别统计出正数和负数绝对值最大和最小的数值。四个变量来记录。这样复杂度应该4n+2

8 楼 抛出异常的爱 2013-03-09  

duoduodeai 写道

gaopenghigh 写道

都是非负整数，那不就是最大值减去最小值吗？  

不是，gao_xianglong已经给出算法了，也谢谢你的回复，小弟谢过了

不是最大减最小的测试用例？

7 楼 gaopenghigh 2013-03-09  

题目
“给出一个以0为起始索引的非空数组 A 其中包含 N 个非负整数，返回数组 A 中任意两个元素之差的绝对值的最大值:”
没有要求是紧挨着的两个元素之差呀？

duoduodeai 写道

gaopenghigh 写道

都是非负整数，那不就是最大值减去最小值吗？  

不是，gao_xianglong已经给出算法了，也谢谢你的回复，小弟谢过了

6 楼 duoduodeai 2013-03-09  

gaopenghigh 写道

都是非负整数，那不就是最大值减去最小值吗？  

不是，gao_xianglong已经给出算法了，也谢谢你的回复，小弟谢过了

5 楼 gaopenghigh 2013-03-09  

都是非负整数，那不就是最大值减去最小值吗？