编程

当前位置:时时彩平台 > 编程 > 百度面试题:求绝对值最小的数

百度面试题:求绝对值最小的数

来源:http://www.mrmtshipyard.com 作者:时时彩平台 时间:2019-09-27 14:40

  笔试题目:假设一整型数组存在若干正数和负数,现在通过某种算法使得该数组的所有负数在正数的左边,
且保证负数件和正数间元素相对位置不变。时空复杂度要求分别为:o。

有一个已经排序的数组(升序),数组中可能有正数、负数或0,求数组中元素的绝对值最小的数,要求,不能用顺序比较的方法(复杂度需要小于O(n)),可以使用任何语言实现

例如
-3 4 2 -1 7 3 -5
排序后
-3 -1 -5 4 2 7 3

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

  /*1.0版本思想*/

 

  考虑复杂度,我的实现方法是找到第一个postive,再找到第一个negativeafter thepostive,然后进行类似一趟冒泡的排序,重复做下去,直到cann't find negative after the first postive.

算法实现的基本思路

  2.0版本是对1.0版的优化

找到负数和正数的分界点,如果正好是0就是它了,如果是正数,再和左面相邻的负数绝对值比较,如果是负数,取取绝对值与右面正数比较。还要考虑数组只有正数或负数的情况。

#include<stdio.h>void swap(int *a,int *b){    int temp=*a;    *a=*b;    *b=temp;}int main(){    int a[7]={        -3,4,2,-1,7,3,-5    };    /*2.0版本*/    int length=sizeof/sizeof(int);    int i,temp;    for(i=0;i<length;i++){        if(a[i]<0){            temp=i-1;            while(temp>=0 && a[temp]>0){                swap(&a[temp+1],&a[temp]);                temp--;            }        }    }    /*1.0版本 写的有点笨重*/     /*    int pos_fir=-1,p,i;    int n=sizeof/sizeof;    int temp;        while(a[++pos_fir]<=0);//找到第一个正数位置     p=pos_fir;        while{        while(a[++p]>0);//find first negative after first postive                if{ //类似与一趟冒泡             for(i=p;i>pos_fir;i--){                temp=a[i];                a[i]=a[i-1];                a[i-1]=temp;            }            p=pos_fir++;         }            }*/    for(i=0;i<length;i++)        printf("%d ",a[i]);        }

我根据这个思路用Java简单实现了一个算法。大家有更好的实现方法欢迎跟帖

public class MinAbsoluteValue 
{
    private static int getMinAbsoluteValue(int[] source)
    {

        int index = 0;
        int result = 0;  
        int startIndex = 0;
        int endIndex = source.length - 1;
        //  计算负数和正数分界点
        while(true)
        {
                //  计算当前的索引
            index = startIndex + (endIndex - startIndex) / 2;
            result = source[index];
                //  如果等于0,就直接返回了,0肯定是绝对值最小的
            if(result==0)
            {
                return 0;
            }
                //  如果值大于0,处理当前位置左侧区域,因为负数肯定在左侧
            else if(result > 0)
            {
                if(index == 0)
                {
                    break;
                }
                if(source[index-1] >0)
                    endIndex = index - 1;
                else if(source[index-1] ==0)
                    return 0;
                else
                    break;
            }
                //  如果小于0,处理当前位置右侧的区域,因为正数肯定在右侧的位置
            else
            {
                if(index == endIndex)
                    break;
                if(source[index + 1] < 0)
                    startIndex = index + 1;
                else if(source[index + 1] == 0)
                    return 0;
                else 
                    break;
            }
        }
        //  根据分界点计算绝对值最小的数
        if(source[index] > 0)
        {
            if(index == 0 || source[index] < Math.abs(source[index-1]))
                result= source[index];
            else
                result = source[index-1];
        }
        else
        {
            if(index == source.length - 1 || Math.abs(source[index]) < source[index+1])
                result= source[index];
            else
                result = source[index+1];
        }


        return result;
    }
    public static void main(String[] args) throws Exception
    {

        int[] arr1 = new int[]{-23,-22,-3,-2,1,2,3,5,20,120};
        int[] arr2 = new int[]{-23,-22,-12,-6,-4};
        int[] arr3 = new int[]{1,22,33,55,66,333};
        int value = getMinAbsoluteValue(arr1);
        System.out.println(value);
        value = getMinAbsoluteValue(arr2);
        System.out.println(value);
        value = getMinAbsoluteValue(arr3);
        System.out.println(value);
    }
}

 上面的代码分别输出1、-4和1

 

 

本文由时时彩平台发布于编程,转载请注明出处:百度面试题:求绝对值最小的数

关键词:

上一篇:没有了

下一篇:没有了