• 2015百度笔试题(算法)

    2015/10/16 王先生 32 评论

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

2 2 收藏


直接登录
最新评论
  • Adrian 数据挖掘,用户画像 2015/10/17

    先判断两头,区分情况,在二分查找:

    import os
    import sys
    import math

    list1 = [-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7]
    list2 = [0,1,2,3,4,5,6,7]
    list3 = [-5,-4,-3,-2,-1]

    def find_min_abs(list):
    if len(list) = 0:
    return list[0]
    elif list[-1]<=0:
    return abs(list[-1])
    else:
    half = int(len(list)/2)
    low = list[:half]
    high = list[(half+1):]
    return min(find_min_abs(low),find_min_abs(high))

    if __name__ == "__main__":
    print find_min_abs(list3)

  • 阿迷   2015/10/17

    = 0) {
    return $arr[0];
    }

    //全是负数,则绝对值最小是最后一个数字
    if (($end = end($arr)) $val) {
    if ($val >= 0 ) {
    $k = $key;
    break;
    }
    }
    //下标是k 和 下标是k-1 做比较
    if ($arr[$k] >= abs($arr[$k – 1])) {
    return $arr[$k – 1];
    }
    return $arr[$k];
    }

    • 阿迷   2015/10/18

      前面部分被删除了,这是前面部分的代码
      = 0) {
      return $arr[0];
      }

      • 阿迷   2015/10/18

        奇怪,部分代码还是被删了,发布不了
        前面部分被删除了,这是前面部分的代码
        $arr1 = [4,6,9,11,12,15];
        $arr2 = [-20,-18,-10,-9,-4];
        $arr3 = [-10,-5,1,3,9];

        //结果1: 4, 结果2: -4, 结果3: 1
        echo sprintf(‘结果1: %s, 结果2: %s, 结果3: %s’,
        get_min($arr1),
        get_min($arr2),
        get_min($arr3));

        function get_min($arr) {
        //分为3中情况,全是正数,全是负数,正负数都有
        //大于或等于0的话,最新就是第一个
        if ($arr[0] >= 0) {
        return $arr[0];
        }

  • 简单,二分法头尾相减,递归一下,复杂度O(lgN),如果用二进制位移可能还有更快的方法。

  • 王先生 学生 2015/10/18

    具体思路如下(供大家参考)
    1.数组中的元素全为正,取最左边的数字;
    2.数组中的元素全为负,取最右边的数字的绝对值;
    3.数组中有正数有负数,就用二分法查找,判断中间元素的符号
    a)中间元素为正,继续判断中间元素前面一个元素的符号
    b)中间元素为负,判断中间元素后一个元素的符号
    c)中间元素为零,令其等于结果值返回

    • Cmder Cmder 2015/10/19

      嗯嗯,这种思路把所有的情况都罗列进去了!不错!

    • 疯小子 一个糟糕的程序猿 2015/10/20

      你提供了很好的思路,以下是我用javascript实现的
      //取绝对值最小的数组元素
      Array.prototype.absMin = function () {
      //数组升序排列
      this.sort(function (a, b) { return a > b; });
      //初始化查询范围
      var front = 0, end = this.length – 1, mid;
      //循环缩小查询范围以达到目标值
      while (front = 0) {
      break;
      }
      //全部非正
      else if (this[end] 0) {
      end = mid;
      }
      //查询范围已经压缩到最小 (必须,否则死循环)
      else if (front == mid) { //或front + 1 == end
      if (Math.abs(this[front]) < Math.abs(this[end])) {
      break;
      }
      else {
      front = end;
      break;
      }
      }
      else {
      front = mid;
      }
      }
      return this[front];
      //return { index: front, value: this[front], minAbs: Math.abs(this[front]) };
      }
      var arr = [-8,15,-2.1,3.5,7,-11,10];
      arr.absMin();
      //得-2.1

  • BlackJoker   2015/10/19

    绝对值最小,其实就是离原点0最近的点,自然用二分法。复杂度是O(log2 N)

  • IT狗   2015/10/20

    第一感觉是二分法,比较条件改一下,改为middle元素绝对值是否进一步缩小;

    于是问题来了,多少人能够写对二分法:
    1. 比较的是mid =low + (hight-low)/2, 如果是(hight+low)/2则求和可能溢出
    2. 进一步变化时hight=mid-1;low=mid+1; 任何一个不多变化1(直接赋值mid)都将导致死循环;

  • IT狗   2015/10/20

    第二感觉:具体分析这个问题的特点,假设数据递增,那么从第一个元素开始,找到第一个非负得情况,综合前后2个数就可以得到数列最小绝对值

  • 三分法求极值。

  • cbic   2015/10/20

    #include
    using namespace std;

    double searchmin(double*, int, int);
    int main()
    {
    double L[] = {-10, -5,1,3,9};
    double minL = searchmin(L, 0, sizeof(L)/8-1);
    cout << "min=" << abs(minL )<< endl;
    return 1;
    }

    double searchmin(double* arr, int low, int high)
    {
    if (arr[high] = 0)
    return arr[low];
    int mid = (low + high) / 2;
    if (arr[mid] * arr[mid – 1] abs(arr[mid – 1]) ? arr[mid – 1] : arr[mid];
    if (arr[mid] * arr[mid +1] abs(arr[mid +1]) ? arr[mid + 1] : arr[mid];
    if (arr[mid] > 0)
    return searchmin(arr, low, mid – 1);
    else
    return searchmin(arr, mid + 1, high);

    }

  • cinuor   2015/10/20

    def minAbsolute(l = None):
    if l is None:
    raise ValueError(‘List should not be null’)
    low = l[0]
    high = l[-1]
    mid = None
    while l.index(low) < l.index(high):
    mid = l[(l.index(low) + l.index(high))//2]
    if abs(l[l.index(mid)-1])<abs(mid) and abs(mid) abs(mid) and abs(mid) > abs(l[l.index(mid)+1]):
    low = l[l.index(mid)+1]
    else:
    return mid
    if l.index(low) == l.index(high):
    return low

    还是二分法,算法复杂度为O(logN),我认为可以看做是一个V字形,绝对值最小的就是V最下面那个尖的地方,\_/这种情况和V字形的差不多。比较的时候比较mid和旁边两个节点的关系,如果abs(mid-1) < abs(mid) abs(mid) > abs(mid+1),那么low指向mid+1;当abs(mid-1) abs(mid+1)的时候,mid就是绝对值最小的。当abs(mid-1) == abs(mid) 或者abs(mid) == abs(mid+1)的时候,就是\__/这种情况。

  • BlackJoker   2015/10/21

    前面的评论犯了经验主义错误,二分法是,正确答案是用三分法求极值,@一叶扁舟不惧风雨 的评论提醒了我。我特意写了一篇博客详细介绍三分法,并附上本题答案的Java代码:http://www.debug4.me/Algorithm/ternary-search/

    • BlackJoker   2015/10/21

      二分法是错误的

    • sundance   2015/10/21

      没用过三分法。。。。去百度了一下啊三分法是干什么的:三分法——求解凸性函数的极值问题。。。。。。你怎么判断这个数组是凸函数?然后你的程序{-1,-1,-1,0}测试有错。

      • BlackJoker   2015/10/21

        取绝对值以后,这个数组就是凸函数(下凸),自变量是数组的索引,因变量是元素的绝对值。

      • BlackJoker   2015/10/21

        另外,{-1,-1,-1,0}不是升序的..,这个数组的绝对值不满足下凸的条件。

        • sundance   2015/10/21

          {-1,-1,-1,0}不是升序的?那{-2,-1,-1,-1,0}?然后你这里说的凹凸性不是数学里面求极值的凹凸性的概念。

          • BlackJoker   2015/10/21

            绝对值,绝对值,绝对值,重要的事情说三遍。

            • sundance   2015/10/21

              。。。。。数学的凹凸性指的是二阶导大于还是小于0。。。。你取了绝对值之后确实在接近0的地方有一个凹点。。。。但是你没办法保证其他地方的凹凸性是一致的。。。。好吧。。。其实我也没有别的意思。。。。就是想说这个用二分法写不出来的算法搞的应该都不怎么样的。。。。
              public static int findMin(int[] data){
              int left = 0;
              int right = data.length – 1;
              int temp;
              while(left 0){
              right = temp / 2;
              }else if(data[temp / 2] 2 * data[right]){
              return data[right];
              }else{
              return data[left];
              }
              }

              • BlackJoker   2015/10/21

                1,其他地方的凹凸性必然是:下凸的;
                2,导数是连续函数的概念,但我们面对的是数组,是离散的,所以才会出现数组[…,-1,1,…]的正确结果有两个值:-1和1,如果是连续函数则只可能是一个值,这时按照三分法,相当于把区间缩减到了[-1,1];当然凸性也是连续函数的概念。
                3,二分法不适合这个题,二分法处理的是有序数组,而这个题处理的数组是先降序后升序的

                • sundance   2015/10/21

                  1、你高数没学好
                  2、函数凹凸性只和二阶导有关,散点图没有凹凸这一说
                  3、我已经把二分法代码贴出来了,你自己粘过去运行看看

            • sundance   2015/10/21

              奇怪。。。代码贴出来有问题。。。
              public static int findMin(int[] data){
              int left = 0;
              int right = data.length – 1;
              int temp;
              while(left 0){
              right = temp / 2;
              }else if(data[temp / 2] 2 * data[right]){
              return data[right];
              }else{
              return data[left];
              }
              }

            • sundance   2015/10/21

              把大于小于改成相应符号就行了
              public static int findMin(int[] data){
              int left = 0;
              int right = data.length – 1;
              int temp;
              while(left 小于 right – 1){
              temp = left + right;
              if(data[temp / 2] 大于 0){
              right = temp / 2;
              }else if(data[temp / 2] 小于 0){
              left = temp / 2;
              }
              }
              if(data[right]-data[left] 大于 2 * data[right]){
              return data[right];
              }else{
              return data[left];
              }
              }

          • BlackJoker   2015/10/21

            {-1,-1}这种不算严格递增(严格单调)

  • 其实就是一个变形的二分查找,并不需要三分法:

    def find_min_abs(data):
    left = 0
    right = len(data) – 1

    while left < right – 1:
    mid = (left + right) / 2
    if data[mid] 0:
    right = mid
    else:
    return 0

    if abs(data[left]) > abs(data[right]):
    return data[right]
    else:
    return data[left]

    if __name__ == ‘__main__’:
    test = [-5, -1, 2, 3]
    print find_min_abs(test)