讨论/技术交流/求大神指教一道面试题 二维整形数组/
求大神指教一道面试题 二维整形数组

二维整形数组
每一行和每一列元素值都是有序(相邻可能相等)
给一个目标元素,查找这个元素出现过的所有位置下表输出

双层for 挨个遍历元素暴力破解忽略,要求用相对高效的算法,我考虑过为子数组进行2分查找这样会相对提高速度,求大神赐教除暴力破解以外的方法

$arr = [
    [1,1,2,3],
    [1,3,4,4],
    [3,4,5,7],
];
$target = 4;
//返回的结果,结果不一定非要是数组只要输出的目标元素下标位置能对就行
$res = [
    [1,2],
    [1,3],
    [2,1],
];

//加分项如果方法同时满足一下输入更加完美
$arr = [
    [1,1,2,3,5,7],
    [1,3,4,4,4,5],
    [3,4,5,7,8,9],
];
共 9 个回复

那这样的话每一列的元素值是有序的条件就被破坏了(新加的后两列不满足),此时只有每一行是有序的,那可能考虑对每一行进行二分查找。

题目没错,面试的时候给的就是这个示例

对每行(列)二分查找,适当剪枝,O(mlogn)。
想不到更高效的了。

力扣原题,右上角看成root的二叉搜索树

$arr = [
    [1,1,2,3,5,7],
    [1,3,4,4,4,5],
    [3,4,5,7,8,9],
];

观察一下最后这个样例可以发现最后两列是无序的,看看题目样例是不是给错了吧。
总体思路上来说应该二分就是最快的了,感觉上来说和剑指offer的题目还是比较像的

一样的呀,有序就是递增或相等阿

这是我目前能想到的相对暴力破解高效一点的方法,如有错误还望指教

$keys = [];

foreach ($arr as $key => $val) {
    print_r($val);
    $len = count($val);
    $high = $len - 1;
    $lower = 0;
    while ($lower <= $high) {
        $middle = intval(($lower + $high)/2);
        if ($val[$middle] > $target) {

            $high = $middle-1;
        } else if ($val[$middle] < $target) {

            $lower = $middle+1;
        } else {

            $keys[] = [$key, $middle];
            for ($i = $middle+1; $i < $len; $i++) {
                if ($val[$i] > $target) {
                   break;
                }

                $keys[] = [$key, $i];
            }
            for ($j = $middle-1; $j > 0; $j--) {
                if ($val[$j] < $target) {
                    break;
                }
                $keys[] = [$key, $j];
            }

            break;
        }

    }
}
print_r($keys);

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
你说的是这道题吗?不一样的,链接里的题 从左到右,从上到下都是递增的,我遇到的这个面试题不是

这不是剑指offer的题吗,从左下角或者右下角开始找。
例如从左下角开始,比target大就往右移,比target小就往上移,最终可以找到想要的数。
时间复杂度尾为o(m+n)