当前位置：首页 > article >正文

寻找目标值（最优解）

article 2024/12/28 9:48:20

题目来源

LCR 121. 寻找目标值 - 二维数组 - 力扣（LeetCode）

题目描述

m*n 的二维数组 plants 记录了园林景观的植物排布情况，具有以下特性：

每行中，每棵植物的右侧相邻植物不矮于该植物；
每列中，每棵植物的下侧相邻植物不矮于该植物。

请判断 plants 中是否存在目标高度值 target。

示例 1：
输入：plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8

输出：true
示例 2：
输入：plants = [[1,3,5],[2,5,7]], target = 4

输出：false

题目限制

最优解

时间复杂度O(n*m)

思路分析

1. 常规暴力思路及其不足

暴力思路：最直接的方法是遍历整个二维数组。通过两层嵌套循环，外层循环遍历行，内层循环遍历列，对数组中的每一个元素都进行检查，看其是否等于目标值 target。
不足：这种方法的时间复杂度为，当数组规模较大时，效率较低。因为我们没有利用到数组元素有序排列的特性。

2. 高效查找思路：从右上角开始搜索

起始位置选择：选择数组的右上角元素 plants[0][n - 1] 作为起始搜索位置。这是因为该位置具有特殊的性质，它在所在行中是最大的，在所在列中是最小的。
比较与移动策略：
- 相等情况：当当前元素 plants[row][col] 等于目标值 target 时，说明找到了目标值，直接返回 True。
- 当前元素大于目标值：由于当前行中，当前元素右侧的元素都不小于它，所以右侧元素肯定都大于目标值，不可能是我们要找的目标，因此可以向左移动一列（即 col -= 1），继续在新的列上进行比较。
- 当前元素小于目标值：因为当前列中，当前元素下方的元素都不小于它，所以下方元素都大于目标值，我们需要向下移动一行（即 row += 1），在新的行上继续查找。
终止条件：当行索引 row 超出数组的行数（即 row >= m）或者列索引 col 小于 0 时，说明整个数组中不存在目标值，返回 False。

通过这种方式，每次比较后我们都能有效地排除一行或一列，大大减少了搜索空间，使得时间复杂度降低到，相比于暴力搜索有了显著的性能提升。

例如，对于示例 1 中的数组 plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]] 和目标值 target = 8：

从右上角元素 plants[0][3] = 8 开始，它恰好等于目标值，直接返回 True。

再看示例 2 中的数组 plants = [[1,3,5],[2,5,7]] 和目标值 target = 4：

起始于右上角元素 plants[0][2] = 5，因为 5 > 4，向左移动一列，此时 col = 1。
比较 plants[0][1] = 3，由于 3 < 4，向下移动一行，此时 row = 1。
比较 plants[1][1] = 5，因为 5 > 4，向左移动一列，此时 col = 0。
比较 plants[1][0] = 2，由于 2 < 4，向下移动一行，此时 row = 2，超出了数组的行数，所以返回 False。

这种基于数组特性的查找思路，能够帮助我们在有序二维数组中高效地定位目标值。

具体代码

class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        if(plants.size()==0)return false;
        int m=plants.size();
        int n=plants[0].size();
        int i=m-1,j=0;
        while(i>=0 && j<=n-1)
        {
            if(plants[i][j]>target)
            {
                i--;
            }
            else if(plants[i][j]<target)
            {
                j++;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
};

这段 C++ 代码定义了Solution类中的findTargetIn2DPlants函数，用于在二维数组plants中查找目标值target。先检查数组是否为空，若空则直接返回false；接着获取数组行数m和列数n，从左下角元素开始搜索，通过循环比较当前元素与target，大于target时向上移动一行，小于target时向右移动一列，相等则返回true，循环结束未找到则返回false ，利用数组特性实现高效查找。