菜鸟笔记
提升您的技术认知

剑指offer

《剑指Offer》刷题目笔记

剑指Offer 数组

《剑指Offer》二维数组中的查找《剑指Offer》旋转数组的最小数字《剑指Offer》调整数组顺序使奇数位于偶数前面《剑指Offer》数组中出现次数超过一半的数字《剑指Offer》连续子数组的最大和《剑指Offer》把数组排成最小的数《剑指Offer》数组中的逆序对《剑指Offer》数字在排序数组中出现的次数《剑指Offer》数组中只出现一次的数字《剑指Offer》数组中重复的数字《剑指Offer》构建乘积数组

剑指Offer 字符串

《剑指Offer》替换空格《剑指Offer》字符串的排列《剑指Offer》第一个只出现一次的字符《剑指Offer》左旋转字符串《剑指Offer》翻转单词顺序序列《剑指Offer》把字符串转换成整数《剑指Offer》正则表达式匹配《剑指Offer》表示数值的字符串

剑指Offer 链表

《剑指Offer》从尾到头打印链表《剑指Offer》链表中倒数第k个结点《剑指Offer》反转链表《剑指Offer》合并两个排序的链表《剑指Offer》复杂链表的复制《剑指Offer》两个链表的第一个公共结点《剑指Offer》链表中环的入口结点《剑指Offer》删除链表中重复的结点

剑指Offer 树

《剑指Offer》重建二叉树《剑指Offer》树的子结构《剑指Offer》二叉树的镜像《剑指Offer》从上往下打印二叉树《剑指Offer》二叉树中和为某一值的路径《剑指Offer》二叉树的深度《剑指Offer》平衡二叉树《剑指Offer》二叉树的下一个结点《剑指Offer》对称的二叉树《剑指Offer》按之字顺序打印二叉树《剑指Offer》把二叉树打印成多行《剑指Offer》序列化二叉树

《剑指Offer》二维数组中的查找

阅读 : 3671

题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例:

比如在下面的二维数组中查找数字7,查找过程如下:

二维数组中的查找

给定 target = 7,目标值 7 在这个数组中,返回 true 即可。

给定 target = 20,目标值 20 不在这个数组中,需要返回 false 。

题目分析

这个二维数组是有特点的:

每一行都是递增
每一列都是递增

首先,我们初始化一个指向矩阵右上角的 元素 。

从这个元素开始查找,如果这个元素比 target 大,则说明需要找更小的,往左走;如果这个元素比 target 小,则说明应该找更大的,往下走。

代码实现(c++)

class Solution {
public:
    bool find(int target, vector<vector<int> > array) {
        int rows = array.size();
        int cols = array[0].size();
        if(!array.empty() && rows > 0 && cols > 0){
            int row = 0;
            int col = cols - 1;
            while(row < rows && col >= 0){
                if(array[row][col] == target){
                    return true;
                }
                else if(array[row][col] > target){
                    --col;
                }
                else{
                    ++row;
                }
            }
        }
        return false;
    }
};

代码实现(java)

public class Solution {
  public boolean Find(int target, int [][] array) {
    //边界条件判断
    if (array == null || array.length == 0 ||
      array[0] == null || array[0].length == 0)
      return false;
    //获取函数矩阵的行数 m 与列数 n
    int m = array.length, n = array[0].length;
    //初始化一开始的元素位置,这里我们设置为矩阵最右上角的元素
    int i = 0, j = n - 1;
    //循环遍历整个函数
    while (i < m && j >= 0) {
      //如果目标值小于右上角的数字,则列下标减一
      if (target < array[i][j]) j--;
      //如果目标值大于右上角的数字,则行下标加一
      else if (target > array[i][j]) i++;
      //如果相等,直接 true
      else return true;
    }
    //循环结束后如果还没有找到目标时,返回 false
    return false;
  }
 }

代码实现(Python2.7)

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)
        cols = len(array[0])
        if rows > 0 and cols > 0:
            row = 0
            col = cols - 1
            while row < rows and col >= 0:
                if target == array[row][col]:
                    return True
                elif target < array[row][col]:
                    col -= 1
                else:
                    row += 1
        return False

复杂度分析

  • 时间复杂度:O(n+m) 。在循环语句中,除非直接返回结果,否则每一次行都会递减一次或者列都会递增一次。该矩阵共有 m 行 n 列,因此循环终止之前,循环不会运行超过 n+m 次。其它的操作都是常数,所以总的时间复杂度是线性的。
  • 空间复杂度:O(1)。没有使用额外的存储空间,所以它的内存占用是恒定的。