黑马程序员技术交流社区

标题: 【上海校区】百度面试题：求一个已排序的数组中绝对值... [打印本页]

---

作者: 不二晨    时间: 2019-4-8 13:23
标题: 【上海校区】百度面试题：求一个已排序的数组中绝对值...
题目为：
有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现

例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。

这一题该如何求呢？

初步的解决思路是：

    1.数组中的元素全为正，取最左边的数字；

    2.数组中的元素全为负，取最右边的数字的绝对值；

    3.数组中有正数有负数，就用二分法查找，判断中间元素的符号

       a)中间元素为正，继续判断中间元素前面一个元素的符号

       b)中间元素为负，判断中间元素后一个元素的符号

       c)中间元素为零，令其等于结果值返回

下面是根据上面的想法的代码实现，应该还会有漏洞


#include "stdafx.h"
#include <iostream>

using namespace std;

//求取数组中绝对值最小的数字
int minAbsolute(int arr[],int size);
//返回两个数中较小的数
int compare(int a,int b);
int _tmain(int argc, _TCHAR* argv[])
{
        int a[10] = {-10,-8,-5,-3,2,5,8,9,11,15};       
        int size = sizeof(a)/sizeof(int);
        int result = minAbsolute(a,size);
        cout<<"绝对值最小的数是："<<result<<endl;
        return 0;
}

int minAbsolute(int arr[],int size)
{
        int first,last,mid;       
        first = 0;
        last = size - 1;
        int result;

        //数组中的数全是负数，取最右边的数
        if (arr[0] < 0 && arr[size-1] < 0)
        {
                result = arr[size-1];
        }
        //数组中的数全是正数，取最左边的数
        else if (arr[0] > 0 && arr[size-1] > 0)
        {
                result = arr[0];
        }
        //数组有正有负，二分查找
        else
        {
                while(first < last)
                {
                        int mid = (first + last)/2;
                        if (arr[mid] > 0)
                        {
                                if (arr[mid - 1] > 0)
                                {
                                        last = mid - 1;
                                }
                                else if(arr[mid - 1] < 0)
                                {
                                        result = compare(-arr[mid - 1],arr[mid]);
                                        break;
                                }
                                else
                                {
                                        result = arr[mid - 1];
                                        break;
                                }
                        }
                        else if (arr[mid] < 0)
                        {
                                if (arr[mid + 1] < 0)
                                {
                                        first = mid + 1;
                                }
                                else if (arr[mid + 1] > 0)
                                {
                                        result = compare(-arr[mid],arr[mid+1]);
                                        break;
                                }
                                else
                                {
                                        result = arr[mid + 1];
                                        break;
                                }                               
                        }
                        else
                        {
                                result = arr[mid];
                                break;
                        }
                }
        }
        return result;
}

int compare(int a,int b)
{
        if (a > b)
        {
                return b;
        }
        else
        {
                return a;
        }
}

---------------------
【转载，仅作分享，侵删】
作者：longshengguoji
原文：https://blog.csdn.net/longshengguoji/article/details/8554386
版权声明：本文为博主原创文章，转载请附上博文链接！

---

作者: 不二晨    时间: 2019-4-10 14:23
奈斯，感谢分享！

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2