－－－－－－－－－－－－－－－－－－－－－－

sesame0816

－－－－－－－－－－－－－－－－－－－－－－

deadlylight

不就是找出最大值和最小值么,当然是O(n)咯

xiyoubbs

是要找出相邻两数的最大差值，不是两数的最大差值吧。。。。。

sesame0816

原帖由 xiyoubbs 于 2008-10-15 21:29 发表
是要找出相邻两数的最大差值，不是两数的最大差值吧。。。。。

对:wink:

wucaizhen

关注中...

yuyongyu

1.遍历一遍数组，找出最大值和最小值，时间复杂度O（1.5n)
2.将最大值和最小值之间的区间等分成n-1个小区间，每个区间大小 delt = (max-min)/(n-1)，第i个区间[min+delt*(i-1),min+delt*i)
(根据抽屉原理，排序后相邻数的差大于等于delt，所以如果2个数 在同一个delt内，就可以不考虑)
3.扫描数组，将每个数放到相应的区间中（这里有点桶排序的思想）
4.找出每个区间的最大值和最小值，如果该区间为空，则标记为空
将每个区间的最大值和他相邻右边区间的最小值作差（如果右边空间为空，则一直找到一个非空的区间）得到t个差值 ，t <=n,求出t个差值最大值即可


第4步时间复杂度为O(n)
因为设每个区间元素个数为mi
则m1+m2+...mn-1 = n-2;
找出每个区间最大最小值
为 1.5（m1+m2+...mn-1) = 1.5n所以时间复杂度O(n)

[[i] 本帖最后由 yuyongyu 于 2008-10-16 15:00 编辑 [/i]]

veking

关注。。。

LS的好复杂

qylhnu

原帖由 yuyongyu 于 2008-10-16 09:00 发表
遍历一遍数组，找出最大值和最小值，时间复杂度O（1.5n)
将最大值和最小值之间的区间分成n-1个小区间，每个区间大小 delt = (max-min)/(n-1)
根据抽屉原理，排序后相邻数的差大于等于delt，所以如果2个数 在同 ...

请问这n-1个区间是按升序或降序排列吗？ 如果是，请问如何再o(n)时间内实现？如果不是，又如何说明 “区间的最大值和他相邻右边区间的最小值作差” 就是解（可能解）呢？

yuyongyu

就是有点桶排序的思想
设这个数组最大值为max,最小值min
则第i个区间为[min+(i-1)*delt,min+i*delt)，即把区间等分成n-1个小区间

wishel

int a[10] = {5,1,7,3,4,18,15,24,20,10};
        int min,max,big,small,result,tempResult1,tempResult2;

        small = min = min(a[0],a[1]);
        big = max = max(a[0],a[1]);
        result = tempResult1 = tempResult2 = big - small;

        cout << "result:" << result << " big:" << big << " small:" << small << endl;
        cout << " tempResult1:" << tempResult1 << " tempResult2:" << tempResult2
                << " max:" << max << " min:" << min << endl;
        cout << "初始化完毕" << endl;
        for (int i=2;i<10;i++) {
                if (a < big && a > small) {
                        tempResult1 = big - a;
                        tempResult2 = a - small;
                        if (tempResult1 > tempResult2) {
                                small = a;
                                result = tempResult1;
                        } else {
                                big = a;
                                result = tempResult2;
                        }
                } else if (a > max) {
                        tempResult1 = a - max;
                        if (tempResult1 > result) {
                                big = a;
                                small = max;
                                result = tempResult1;
                                //cout << "changing2" << endl;
                        }
                } else if (a < small) {
                        tempResult2 = small - a;
                        if (tempResult2 > result) {
                                big = small;
                                small = a;
                                result = tempResult2;
                        }
                }
                min = min(min, a);
                max = max(max, a);
        }
        cout << "result:" << result << " big:" << big << " small:" << small << endl;
        cout << " tempResult1:" << tempResult1 << " tempResult2:" << tempResult2
                 << " max:" << max << " min:" << min << endl;