搜索二维矩阵 II

问题描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。每列的元素从上到下升序排列。

示例:
现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii

思路1

暴力法。复杂度为O(m*n)。

题解

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
     for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        return false;
    }  
};

思路2

每层循环，然后在每层中用二分。最坏时间复杂度为O(n*log(m))。

题解

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        int n = matrix.size();
        if (n == 0) return false;
        int m = matrix[0].size();
        int flag;
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = m - 1;
            int mid;
            flag = false;
            while (left <= right) {
                mid = (left + right) / 2;
                if (target < matrix[i][mid]) {
                    right=mid-1;
                } else if (target > matrix[i][mid]) {
                    left=mid+1;
                } else{
                    flag=1;
                    break;
                }
            }
            if(flag==1){
                break;
            }
        }
        return flag;
    }
};

搜索旋转排序数组

问题描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。

示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array

思路

题目中要求算法时间复杂度必须是 O(log n) 级别->用二分查找。
题目中给出数组在某个点进行了旋转，数组在旋转之前是升序排列的，因此，最小的点即为旋转点。
找到了旋转点之后，将数组至多分为两个二分查找。
在两部分分别进行二分查找后，没找到目标值返回-1，如果找到返回坐标i，i一定大于-1.因此在两部分二分查找的结果中找最大值即可。

题解

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int n = nums.size();
        if(n==0){
            return -1;
        }
        int min = nums[0];
        int flag = 0;
        for (int i = 1; i < n; i++) {
            if (min > nums[i]) {
                min = nums[i];
                flag = i;
            }
        }

        int location1 = refen(-1, nums, 0, flag - 1, target);
        int location2 = refen(-1, nums, flag, n - 1, target);
        return max(location1,location2);
    }

    int refen(int location, vector<int> &nums, int first, int last, int target) {
        int mid;
        while (first <= last && first >= 0 && last <= nums.size()) {
            mid = (first + last) / 2;
            if (target > nums[mid]) {
                first = mid + 1;
            } else if (target < nums[mid]) {
                last = mid - 1;
            } else {
                location = mid;
                break;
            }
        }
        return location;
    }
};