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

2017-09-11

php

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

数组全部为正数时, 绝对值最小的元素是第一位;
数组全部为负值时, 绝对值最小的元素为最后一位;
数组即包含正数, 也包含负数时, 需要找到趋近于0的位置, 找到两边的正数和负数, 比较这两个元素的大小;
数组为空或为一个元素时, 就是该元素或不存在。

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

代码如下：

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;
    }
}

测试样例输出：

zhgxun-pro:ankerbox_finance zhgxun$ php artisan test
1
-2
0
0
zhgxun-pro:ankerbox_finance zhgxun$