• 欢迎访问小澍的博客,编程记录,技术贴以及折腾的日常,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏我的博客吧

剑指offer刷题记——二维数组查找

C++ root 2年前 (2019-03-12) 476次浏览 已收录 0个评论

开篇

满打满算,还有半年的时间就要去找正式工作了,在念硕士的阶段,每天打的不是code,都是一堆命令的kinds of stuff,虽说Python也断断续续用了一年,但是连续写起来,还是要查查这查查拿,更不用说本科阶段入门CS 的C++。 可以用的OJ平台数不胜数,本科时候大家热衷的PTE,现在从国外火到国内的LeetCode(力扣),以及牛客网的在线编程。选定一个就好,此次选择剑指offer,题库共66道,难度适中,适用于让我快速系统的coding。每道题都会坚持使用C++以及Python来完成。虽然平时用的是Python3,平台在线编译只支持2.7,但是作为纯粹的编程练习来说,问题不大。

二维数组查找

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

分析

题目意思非常明确,就是从二维向量中查找制定数字,题目的技巧就在于数字的递增规律。按行来查找,可以从右往左查,如果查到一行中某个位置的数值以及比目标值小,则可直接到下一行继续查找;从列的角度上来说,如果某一个位置的数值已经比目标还大,那么该列剩下的待查找数值一定也比目标值要大(因为是递增关系),所以该列剩余的值就不需要继续查,跳到下一行的时候,列指针不变,继续左移即可。

使用到的知识点

C++

二维向量的操作,长度,size

Python

Python 列表的操作方法

题解

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int row = array.size();
        if(row!=0){
            int col = array[0].size()-1;
            int i = 0,j = col;
            while(i<row && j>=0){
                if(array[i][j] == target)
                    return true;
                else if(array[i][j] > target)
                    j-=1;
                else
                    i+=1;
            }
         }
         return false;
    }
};
class Solution:
    def Find(self, target, array):
        row = len(array)
        if row != 0 :
            col = len(array[0])-1
            row = 0
            while row<len(array) and col>=0:
                if array[row][col] == target:
                    return True
                elif array[row][col]>target:
                    col -= 1
                else :
                    row += 1
        return False

不得不说,用这两种语言同时做一道题,会非常难受和舒服。。。不用写’;’,不用声明变量真香,C++11 真是太麻烦了


XiaoShuBlog , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:剑指offer刷题记——二维数组查找
喜欢 (4)
[gaosirgoo@foxmail.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址