PHP在升序数组中查找绝对值最小的元素

在一个升序排列的数组中, 查找绝对值最小的元素。分析, 数组升序排列, 两边的数值绝对值只会越来越大, 绝对值最小的元素必须在中间趋近于0的地方,因此思路就是不断的遍历数组, 找到趋近于0的这个位置。

这是不久前我在滴滴出行时,面试官让我在纸上写出来的面试题。在一个升序排列的数组中, 查找绝对值最小的元素。分析, 数组升序排列, 两边的数值绝对值只会越来越大, 绝对值最小的元素必须在中间趋近于0的地方,因此思路就是不断的遍历数组, 找到趋近于0的这个位置。考虑四种情况:


1. 数组全部为正数时, 绝对值最小的元素是第一位;

2. 数组全部为负值时, 绝对值最小的元素为最后一位;

3. 数组即包含正数, 也包含负数时, 需要找到趋近于0的位置, 找到两边的正数和负数, 比较这两个元素的大小;

4. 数组为空或为一个元素时, 就是该元素或不存在。


这个题的思路并不难, 一般都会一开始就想到, 关键是面试时如何在纸上正确写出。我在网上搜索了下,发觉这是一道很老的面试题了,遗憾没有为找工作刷过题,当时没能在纸上写出来,但是思路是正确的,就卡在如何处理有正负数时的情况。我想到了用中点来快速遍历,但是一下子没多想,可能还是因为紧张,就没想到`while`循环的数组下标处理方式,而是去设计每次判断中点偏离了解题思路。


```php

namespace App\Console\Commands;


use Illuminate\Console\Command;


/**

 * 测试

 *

 * @package App\Console\Commands

 */

class Test extends Command

{

    protected $signature = 'test';

    protected $description = '测试样例';


    public function handle()

    {

        $arr1 = [1, 5, 8, 10];

        $arr2 = [-4, -3, -2];

        $arr3 = [0];

        $arr4 = [-10, -8, -2, 0, 1, 6, 8];

        $this->info($this->minAbs($arr1));

        $this->info($this->minAbs($arr2));

        $this->info($this->minAbs($arr3));

        $this->info($this->minAbs($arr4));

    }


    /**

     * 在一个升序排列的数组中, 查找绝对值最小的元素

     * 

     * @param array $list 升序排列的有序原数组

     * @return bool|mixed 返回找到的元素或者布尔错误

     */

    public function minAbs($list = [])

    {

        $start = 0;

        $length = count($list);

        // 全部为正数时

        if ($length <= 1) {

            return $list[0] ?? false;

        }

        if ($list[0] >= 0) {

            return $list[0];

        } elseif ($list[$length - 1] < 0) {

            return $list[$length - 1];

        } else {

            // 既然是正序排列的数组, 那么绝对值最小的元素必定是在正数和负数交界处, 比较两个值即可

            while ($start <= $length) {

                // 取中点, floor返回值为float类型, 强制转化类型

                $middle = intval(floor(($length + $start) / 2));

                // 如果中间值是正数, 看上一个值是否为正数

                if ($list[$middle] >= 0) {

                    // 如果上一个值也大于0, 则该位置全部属于正数, 需要往前继续查找

                    if ($list[$middle - 1] >= 0) {

                        $length = $middle - 2;

                    // 如果上一个值是负数, 则绝对值最小的元素在该位置产生

                    } else {

                        return abs($list[$middle]) > abs($list[$middle - 1]) ? $list[$middle - 1] : $list[$middle];

                    }

                // 当前在负值区域

                } else {

                    if ($list[$middle + 1] <= 0) {

                        $start = $middle + 2;

                    // 该处为正值区域, 绝对值最小的元素在该处产生

                    } else {

                        return abs($list[$middle]) > abs($list[$middle + 1]) ? $list[$middle + 1] : $list[$middle];

                    }

                }

            }

        }

        return false;

    }

}

```


测试样例输出:


```bash

zhgxun-pro:ankerbox_finance zhgxun$ php artisan test

1

-2

0

0

zhgxun-pro:ankerbox_finance zhgxun$ 

```

  • 发表于 2017-09-11 11:35
  • 阅读 ( 796 )
  • 分类:PHP基础

0 条评论

请先 登录 后评论
不写代码的码农
广训

1 篇文章

作家榜 »

  1. Kemin 44 文章
  2. golanglover 5 文章
  3. D.Chen 4 文章
  4. salamander 1 文章
  5. 深圳-伟 1 文章
  6. 广训 1 文章
  7. PHP小菜 1 文章
  8. Undefined 0 文章