《剑指Offer》算法题——二维数组查找

时间:2022-05-22 15:07:27

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

class Solution {
public:
bool Find(vector<vector<int> > array, int target) {
int col = array.size();
int i = ;
while (i < col)
{
int j = array[i].size()-;//考虑边界条件
if (j<)
continue;
if (target == array[i][j])
{
return ;
}
else if (array[i][j] > target)
{
while (j > )
{
if (target == array[i][j])
{
return ;
}
j--;
}
}
i++;
}
return ;
}
};

当我们运行时,需要测试边界条件:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAUoAAAEXCAIAAABEW5p7AAAbLUlEQVR4nO2dz2sU6brHexXOos/J6UUvzMC78JxJhMg1KMHYjqe1DZdLj22LROMi0mCjcJAmYOhFHA9ESRxBBDEbF5Vk4+TOKnAxg6DXvttZzeZCshEa8m/cRd9F/Xqr6nmr3uqqrh9vfz/UInlTb1V1pz/1vPVWPf0UGABAUQppHwAAYFRAbwCUBXoDoCzQGwBlgd4AKAv0BkBZoDcAygK9AVAWsd7zz29oR7V6gsfCc67U3yj0qrKrL20ebi6Zv1Q6mtapjOa4AMgRhV84HH+R1bt26ecRnAXC6F3paJzcjDG2tHnoagFgDLGjt1tvWUajtzxeuRljbGnzEBEcjDu03nNrR3e1o7uO6N2uabuXWp/19hutGmNsxvzVXD5fmqd302hO9Jul3kZhsFrSWoWBGZm7rcJgw1isWG01ctG73Nsoas0Jvb3fnLL+IPKYth6AccInervCcrumHd1dazPGWH33rrY7R69G02hODDaKXVbubRT6zalGc4JXlDF9NF7s2r9PaasuvQuDVpkxxqrFgb2mOErDbzD2FE5OTk5OTpiU3qbS889vDKF3q8xYubcxoZ1jtt7VohW9BwF6m391nAgcc2pOMD4H406o6B273savjMlEb+gNQDii683m1oxLcR9ovc+V+qbe3dbQ0RuDcwBoSL1rl37mJ8x0yYV667fQAqfWyMG5NYvWb5ZMgae01QI3YtclF+mNqTUAhIjve+cF3BgDQIAKD6XisRYASAp5DdpOHDNsPtNtAIwTiugNAPACvQFQFugNgLJAbwCUxU/vpc3Dw8ND3GACIKeI9V7ahNkA5Bqh3pWOhnvHAOQa6A2AsvjqjbE5AHmG0rvS0Q4RuQHIPcLojZk1APIOrr0BUBboDYCyQG8AlAWPtQCgLH4Ppeoz6HAcgJyClBIAlAV6A6As0BsAZYHeACgL9M4e6VZWzznGlxTgli5jLFd6T2lfCr122kfhYDSHlG5l9VyD4hVOxk7vWD8A6R4SoXelo0nex5RfM0+geoWThPRuvJgYfCk1zF+7e4X+iynGGKuV+seFwXFhcOzwpLtnNA6Oi129+3GBWyY0vagZ1b27V+i9sNr5umWOR3UyeEgsjsrq8o8jSa65sv27xfaK3bi9vn7gbBY1urpX1w9+P1g368c5f4sI9HaSWPQu9ywBWLlnfMStHxwrdPcKg72yZwueUFkr9R1Scd1Nb7t7VhfvhzmDh2RsJWJldfkHisM9elxdP+ClNaVc2TZayUaq+8q2tR63TdHx8QQcKypYOElucG6Fx8aLCUMVLtBxAZC3jsftkr0dc/v6Xzl/TASf4gweEmMsntLLMQZxPv7ygdojJdko6q77XV0/iCl0L21iRs1DgtfetVL/S6nBprQvpirtIj88NhmBS4zR//4MHhJj0fWONXrTkVZab0GgNrSmTwiu45OP3phZc5Hk1NqU9mVCa+tG6ZR7x97P/ZT2hRwJc5fHOuKRsGi6yxOoMnhILGJl9ZivvblL45Xt8NFb0J0xtrJ9sL4eYHdocO3tJNmZ83bRNV/lGAzbjk1pXxzzWJ6VuWDravF1iXlP8Nk6pKiV1Ucxc24Nrnkd5QfnZHfrD/HaDb1d5OjGGFALbtgeG9DbCfQGqbCyHXvoZrj4dgO9QdLow/XYI7eOMRkHxxlj0BsAhYHeACgL9AZAWaA3AMqigt4qpfhiZgjESP71dt8LWeh8/PW3P8zlfTOge+snY82Pjy4HrmMuWy2JDQbu3V7zJ6fNuHsL4iH/ertdWOh89NWP4/Kzd35W0zS3/njXuerzV8tV3zWvPtqx1mz95DoMJD6BWBhnvf1Fpbn87J1vTF7ofPx159kCY4S0Dlo/cdtxHwn0BrGghN4OFfjBua+9Vx/tfHy09OydvrLhZABSZ4Sl95IjcyN6X3727jeP3hidg+jkWu+AFN/Lz955Lms5rj7asa2W8jYodDPj5PK+yXTJfUf+l+0zyyPv3isdDQViQERyrTdj/k8ZX32043/1y+m39D5oSO+/NXsd/tpb7jLB0YsxRG8QE7nX20cFd/x0B3vuKt2lLjUsWHpPjbdda/LbkdimdRiuSwPi2htfRgLCo57e3LW3a2ys31PmFbn6aIe810WvSYVuz5rWkDtom/ZxeiM8obf3kAAIQj29/VeVFCTdNcmZ8xDdAdDJv95yKb568JM5D6S7JmPMe8YK2R0Ag/zrrdaDnCq9FpA6KugNACCB3gAoC/QGQFmgNwDKooLeKuV7RwQzc4An/3q7bowNmZstfjTdwHgKxbE1+6mYwOfVqe50o2x3I3GF2DseaQUG+dfb78M8fMY1tR1Xqin3SLnnoXG57t5G+e423qx15JMCHZX1Dkjw8s24pnAKxp0R9AdRgywl/ZTPTvfV2/kyoTfQUUJv+rMcZKxvxjWFQzBLKj1xpfM+MGM8dr2bW4KvkcLoHOjkWm+/LCqJ3OyAjGsPhN5WGtlSCnqbcOcpC6SLA5ZzvRkTPXIuk5vtXl9qds0xOLe/DULG0pHpTX2XE8wGTAG9yc+yVG62jSfjml6TnBtjjHnip1R3cWOI7ubeA6fWkC4+lqiot2xutjjj2r2meZXrutkmujEm1V2wzSG6U9feSBcHTE29/VaNPzc7e92RLg4M8q93evneGezOGEO6OLDIv954EpMDbwXgUUFvAAAJ9AZAWaA3AMoCvQFQFhX0Rr63P5hvG1vyr7f3xljELO5IadihqotTO5IvDx7QHTXDgQJ6uz63MWRxR0nDDlt+2Lt3ufLgZHfUDAdOlNM7Yha3X6NMd/mOwu5S5cHJ7qgZDpwooTf/sY2Wxe3bKNNdurq4eEdS5cHJ7qgZDpzkWm86DSpKFrdvo3x36zBCJpmGKQ9O7h01wwFPrvVmLLi+d1jBfBrlu1t7D3lyCV0e3H/vqBk+7uReb/HHdrgsbnFjyDTsoOriVPfQ5cFFe0fNcMCYinpHzOKOmIYtX12c3pF0efCAvaNmOGAq6u2/an6zuJEEDkKTf73jzvdWrztjDEng40n+9cZDl0Hg/RlbVNAbAEACvQFQFugNgLJAbwCURQW9ke89BJhvGwfyrzdxYyxUNWwvgnxvK5U64FHwUGnYHsjSCPKFxIk1fVLQ8aCq4uRfb/dHNHQ1bCd096Bevt1DpKAvdD5yKV/GmvKFxMnufs/PI0tUbdTTWydENWwKcTkxKUKkYQuxsjtDFxJ3dofeY4wSehOf0BDVsCk84ffjoyU719K/0K+ne+gUdHPN9002TCFxR3f/FHSMztUm13r7ZDyFq4Yd0P3qox3b6mG+ASZkCrrnjBCukLjwNZIp6EgCV5hc682Y8JHzENWwKYjobcX8pfdxpmF7cUsYspC439dIeFLQEb3VJvd6h732dk9uSeVRc7/Gm4bt6U7JGaKQuP9XxHi/AQbX3mqjnt4hq2GHLuUdaxq2qzu3l2EKidPdxSno0Ft11NN7iP75zeIeRRI4UIf86y2X7y3smtss7lEkgQPFyL/eeL5yKPCmjQMq6A0AIIHeACgL9AZAWaA3AMqSnN6YywEgYRKO3rgTA0ByJD04x3MUACRGBvRGpSsARkMKertH59AbgNGQwsw5EowBSIYMRG8AwGjIyrU3nAcgdjKgN6pMAzAaMqA3q3Q0RG8A4iflx1pQZRqA0YGHUgFQFqSUAKAsDr3PAF++ffuW9iEAEILs6V1duPluYY5vufOP5X9d8K4498/F5f26aLn5z38749rI/mK1Gm7XF/9V//c79q/QG+QLQu/JtPnufrV+/5T9++L8cvd00Gqnr+zPT4u2MDtbJ88Cb2a/Izdo7nG6W7+yaK/w7du36K8OgMQo8CP1hPSena1zKlKNp86/mZ+ePH2FjszGat/dr/pEb1vv2dn6frX+xiHq5OTpK/uullPn31TPz05OclZDb5BrCr9wJKO3O7SKGw0W5x1R2gy5UtGbO2tMd41wPd21zxH8XsxG+rRSv38KeoN8YUfvpPQ+fWXfCJJBjQZujTm9paK3zanzbxzx3/On+Wl9s+a1AKI3yDWJ601eSNuNpoHcVbHDsdnZuvOC2Wjcr56ftUfXk1xfznnrr8743D393f3qcnf+yv78tHFdQO0aeoO8kbDehIFEo8Nhx6jbq/d396vcueDUefc1tndf3tA9Od3VL/Xdf4LeINcUTk5OTk5OEtJ7cX7ZG3u9jZzD0926ew7cCv6zs/X9er07X+eGA2a4dlyHy43hdb1F83n15Tez0Bvki0SjtysYChtNvZ2ReXKSuw635slco31za6ev7Nep22l09J6cnHQPE6hjg94gXySot+iyWdTIR/XFedddMQuXgeQZZHJycrqrj/8Nvb0nDugN1CNmvf9vYQELFiwJL0K9473vnfrrxIJlDBeh3vE+tZb668SCZQwXod7xppRY+xt6C5f//vf//vOfZ2dmPpRK//nXv545c+ZNuZyRFqSUgEwRqFvm9P6P06fPT0+fOXNmdmbmf4rF//rLX/73T3/KTkvtb3+L/i4BEAvh9I6Otb8YtwkAIAnUDXoDkFegNwDKkkm9L15o7FfmZBqBPxcvNPbr12+mfRj5ZO5pfXm/vvz0bIxruph5WJPsKL8mTxb1nnlYazz8XqZxWL6vvM3ah340hySrdwbfkLSRDydRA8/Z6/u1ysV41zTIoN7kawj9wnyJ59M887A2xAlbQLqHROxd/nwa65k3M9ysLL+9MBPvmgLmnsr+6+XX1Mme3jcrxAeUa5x5WOPfzbmndeOzdfFCw0ze4t8CY+C0X1/er8xZgxx7Mc8aVPe5p/XrD612xxl67mndOowMHhK/F27XZ6/vVyrm7vSDFO7ds0EfJNfkXnjAKxI1uro73/nvK2/rsZ1o8qL3zcqyeICWNb2/r7z1RmlXIx/Jz143/vfWD44V5p6SlyueYHXxQsMhFdfd/M9x7+zZ6/uuj1EGD4nc7Nnr1vXbzQp3dhCOHWYe1pblRp7ya5qviJPW84oEL9PbnXvn/QfJ3LnSe8IlIMNMxDUF2PFgiDXzpDd5IvQ0Wi/SHou6/3n6v1w0pHd/ml1jWv5DRn2wiHczg4dEbZY74zhk8L00uFlZlrwyClzzZoV7Q7hATb2fxPEIulvvfEyhmzsJxrZmADMPa5JvsvyaLGt6y/6nL15ovL0ww0d1eoA0ApeMzXr+qRk8JGKzofWONXrTkVZab0GgNt55fqxEETJ6y89iRJ+CiRS9fcmS3sb/SaJRt+gm/6ez14l/2PeVt/TJ1f02iUfCog+B52ozg4fEpPWmPzcxX3u7LjHC6i3ozhibe1qrPIw6QnaTq2tvkfMZ0lv0CaMP3XvJwZ+endMtruGcc2Uu2FJzSz7vu/u0na1D4vdiBSuh3t69j2Lm3Jobazy8cD384JzszljA9eeQ5EVv/R8nOLVlRm88ygKGJrJgkbaZ8o0xv/sFmdEbgCEhL4Iik4fHWvSbmj5DJ+gNcow+XB/RQzWjfmI0gV1I6W0RatPD7Q8AEBepRW8sWLAktkBvLFiUXaA3FizKLgnpHcD88xvaUa2e3A7V4Vypv1HoVSNtY2nzcHPJ/KXS0bROJfJxgSyTTb1rl37GWcBJZL0rHY2TmzHGljYPXS1AMZLVWxboHTdeuRljbGnzEBFcZZLTe27t6K52dNcRvds1bfdS67PefqNVY4zNmL+ay+dL86JNLrz+dOvJ6v2vnx5//fT4w+psLMe5sv27xfaK3bi9vn7gbBY1urpX1w9+P1g3467zNy/nSv2NwmCjMNgo9JtTelu3ZbRw0XtKWzUaBxuFwUax6+nOh3qRx4T1S5uHCOqqkHD0doXldk07urvWZoyx+u5dbXeOXk3EwutPj7++XGCMsTu3vn66dU+0YqWjHTqQ+vhW1w94aU0pV7aNVrKR6r6yba3HbZOk2xKNwKe0VfpP3daEdk7/sdyzPGfl3obVLo7S9JAdeitC6nqbSs8/vzGM3qbSlxc/+OgdCj7+8oHaIyXZKOqu+11dP/AL3Yw1mhODjcKgVfb8hda70ZywG7nQPdgoDBx6i4TF+FxlxkPvENGbjrTSegsCtaE1fUIgqBY9klN6V4uOdarFwWqpQWwOeo8p2dSbza0Zl+K+jCB6c5fGK9vho7egO2NsZftgfd3TwWckfK7Ut0fajNK73HPLXO7Rs+uhB+cwXg0S07t26Wd+wkyXXKi3fgtNZmot9sG5NbjmdZQfnJPdrT+41tdHFZxejgkzU1TXLJre7mo0x+H8+JyTP8TUmueYQH7J5o0xFeGG7SkQ4sZYpaMheisC9E6GlW1P6E4Ymcda9MgNt5UBeo8cfbieYuS2cMyw+Uy3AVWA3gAoC/QGQFmgNwDKAr0BUJYs6t3dKwyOC4PjQq897CZqpX6U7gAoQYJ610r9Y8PbwZ73mWoXU9oXGT8Fq0FvAJLTu1bqH09ogY+Z2kTTGwCQvt5cSHda6vK23Ds2H8CulfrHxS5jjRcTA2s4cFwYmNunx/bEjsq946JmbqT/Ysrv+C8vfvj0mEgsR/okyDDJDc4NG79wWRC8827/g/WmVhN0p3dU7lmXCe3i4JjP33Bz7+Xj13eoP0BvkGGSnlrjJW+8mOAvwrt7vKhx6i3YkWibBD/o3wnzEuUZQJ5IZea83Dsu9Np50tvgzi1IDnJEGnpbw+Nwg3P9r1PalwI/kO7ukZfNkoPzkHozT+YpsqNBhklK73aRnwazxbPbLbd1gd0rN+w5sFKPV9GeM+P99+yL2JG83rNP9ox5ta+fnBfhyI4GGSaLj7XkCmRHg+wCvYcH2dEg40BvAJQFegOgLNAbAGWB3gAoC/QGQFmyWQB4bAhb1tdd24CxnH4nIqqLJ0I29R5FAeDZJ3uCtJDRY5X4dFTzZDHoTX9/ebZY6Hz89bc/ft1qOVpRXTwBsjk4V1DvEA774NI7B3I3t/5417m60Pno1hvlzRIg1/W92b2Xj1+vWpnYfEEixwOkP5g1wM3l/pPLcbwkURK4B1Jvqmp3ubdR1PQioVx9b2fpT1tvrx8pFycXQuqN6uIjJ/USglHqe7N7Lx9/3Vv8wfz59R3mKDzGFl7bJstF7zCVwIVJ4B4cg3NH3T9XYcByzyoMWi2aJnOFAR3R2zf6pVGcXAytN6qLj5rU9Y5SAJgSjIuozkAd/+BcPglcPDj36m3aa5nMl/V16+0RIdXi5GIEemN8PmKU0/vOLSueO4k/ett7DJI8Kb2zUZycAHqnQzb1lqzvTQ6PF15/ojW+9zLgCnl4qCRw3rxIep8r9Y36vnrRX/HgPDvFyd2EG5zD+LjIdX1vwdUvPz7nI7ndHsvUmjAJ3JsDTulNVu2m9GasYU629arcCr5TawkUJ5fLdW9u/fHrb9zCS47q4qMmmzfGgByJ3Riji5NHvHWN6uIjB3rnm0QEJ4qTR891R3XxBIDeuWekD6WOqjh5Lp+kzR/QGwBlgd4AKAv0BkBZoDcAypKFhFD7lrjMoywZmpRB0jLINhnQu7579+fnM3Ib8NwHonOJRwD9TCuSlkGWSX9wPtP6bCSNBeKW2yeXOHZEj6zjqWmQXdLM9/akdnMPpVIITBpe71jSxXPwlQpgXEk3pYSxENFbFCedepMpX4I8sHjSxeE3yCr50pu0KFr0jiFdHONzkFGU0ztk9I4jXRx6g4ySL70lBudhiCddHINzkFXSzfdmLMzMucdvv1xiGWJJF4fdILOkf2MsBFk0CSNzkF1ypXf2BMdjLSDL5ExvlqmHUjN0KAAQ5E9vAIAk0BsAZYHeACgL9AZAWaB3EtRaa0c7D9rs2u7O1ueWf+JMmtuMDe5L2qlKiSAhxlzvpKoC//jgaOdBm809fxWfiqPYZly465C7irGAhIDe4fQmb7wH343/8cHRq9s1Nvf81dbuj+EPM6ZtDnnwQwC9s0Hu9b730sruEiZsO9I8zXpgQxT9XtokvmWfbAyk1lo7enXb/OopLgLP3/68s3W0s3W0w0nLNQ4dqIc/eK66uKlouDrktN6o9Tt68q33vZee0pyXFz9Yoto/E3ozxsJE7xjV1rm2u7P2XC+fNn/7886DttH4oO1Zob0WMeZHOXi+qlm5ZxQzDFWHnEHvtMi13vzXLRj8sHqfF574koYh9K50NO8HkWwMQ3vNCMW11po3dB/tbB2Zetdaa0c7W0dr14bZTcSDdwTkwsDWW75QMcPgPC2gd4jo7REiWgCav/351e0aH7GNy2kBPz4YVvIIB89LawO980Gu9Z59sic/ONd/0Kv22rW4QxX9jn2A3l5be956wBl7bXfHdxxuD+NDM+zBc0NuR6N8HXLmMzhHtt1IybXezFlk25T2zi3vbJk1kfZhdZH7NrXQRb9jnnz+8cGRy2d+fG5E8rnnr+wRe5SL8CEPnh+fG/FZvg45Wcbc2jEuvkdL3vXOOf6jccVBKe+RA71TJGgori4o5Z0M0Dsd2muRbmIDIAP0BkBZoDcAygK9AVAW6A2Asoyd3vzXH6abMk3vHTXDQXzkSO8YHmx0P8KRbsq0YO/4cmUQF+Okt/f5rFGkYcsj3DtKI4B4SFBv7tlGPUO40Zzg0hWmtFUzc5hck8hbIlKRG82JfrPU2ygMVktay/EUpJw013Z3HjzXM7S4MbN+m9r5WCiXCsI/Ck7mZpNZ3GKIB0WRPgnCk5ze3RaZmcCLan87FxWlvdGbSEVuNCcGG8UuK/c2Cv3mVKM5YX7ZgGRIvLZrZWXN3/5spWRbkLnZnN5Ubjadxe2H12/oDcKTnN5GBNa/A8Ck27Ljs/WlH+SahN5UKnKjOTFolXnbOb1l7OBV5IbNejKmsfjpTeRmC7K4fcH4HMRA4tfe1aJD3XOl/mqp4YjDgjW9elOpyKPRO+ibVbx5mnxu9jB5I9AbxEAaU2vOXP9ua0JrFj2xmlyT+1ovxshUZF+9JQfn3Jcr6D9zo/T2Gh+99UY9YdOThu04EYScuhMMzmE8CEViejvyft1B2NEiXtMejRNTa3okF+stP7VGjKKtqbXPrdu7rnG4o1GQm01kcftBTK0hOxqEJwM3xuiv+xkBUt+6wA/O04I8ESE7GoQmdb3J7/oZFRKCp6+397EWZEeD4UhTb708jfNyeuQEzbClrTdqhoP4SD16AwBGBfQGQFmgNwDKAr0BUBZa76XNw0PcZQUg54ijd+QaWgCAdPEZnEeprgMASB/oDYCy+OiN0TkA+SZg5hx5SgDkF0RvAJQF194AKAv0BkBZoDcAyoLHWgBQFjyUCoCyFH7hSPtgAABxUkj7AAAAo+L/AZfCXUMkqSl6AAAAAElFTkSuQmCC" alt="" />

如果没考虑到这里,就会向下越界。该算法可以运行,但是这个算法超时:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAjEAAAA0CAIAAAD0X/45AAAK/UlEQVR4nO2cQa77uA3G53hBDhHkEIa33ccHmK2O4WyyqIEC2fkAaQ4xJ5iFLImkSFrOy2uFwQf8ULTv78iSSPEjJbl//PV+AwAAAD3wx/+9BwAAAEAEmgQAAKAXoEkAAAB6AZoEAACgF6BJAAAAegGaBAAAoBegSQAAAHoBmgQAAKAXoEkAAAB6AZoEAACgF6BJAAAAegGaBAAAoBegSQAAAHoBmgQAAKAXoEkAAAB6AZoEAACgF6BJAAAAegGaBAAAoBdaNGl+Xi/POf/30/1cM6z0J2G4X28v/eHc1NbaEtJPvCcN5ttDvFr2fGv/NV3uYzDb2Tpc/uI8v46n+/m0BHV0Rmfm24O37/XE6ed8e8gJZKbZJlObgYY3HhjROu4122SvsJyJgRS/Mt5iztJv+epruggP2fM93a8+YB2VhbCOp8c01w+/pov8exjMaWzzOss09/OJjC4s1jME0jfVM0sjS5AxYQn6K+p52Fns77BIJ9z+594P88Pz83rajRjreKpao/7Z0uGyQNoQQ9tjvj20CfTbsXyvbfL3aauTWpYfe7hBTjYLsRknKyoZb749qAuK0bodK3FENFK1Vs2y5jp5hZQIzp/xOjM/r54h2Vssi+YAVxRu60OMGorvNsZNokmsEefnYdCThsP28lTTVD5nln7DV8uE25H3elud2K3H8WOdjMmQTpqNSpPCcj4tE58TaznYbeqz7WZar+lipmi5TdkT5XlFZd9h8ay2l4cR5zGn1IyqJFiTdmrZflxrZxjW9/yalBTBmmHP4sSXWhzjgOmjTe10qg9Neu/l7/SxJkGSazsaicSg5HYkxCijdQLQfHtszeoenGZW9OTynJWiLfsQ6YOrSc2233e787DquWrK13KmE2OEUnEabxdPjre0mNPCKyOyao5q6g7YS88ZhY38Kkpfe9/3VTEbe75HX/HjOkkdUR0XxBQ9pplmQrZCzM/r5TkN9/FmmaOtThITu/3rOl3qSWbJImlBTUH0yk+8t93nmSfHCTHqpOY21zy3YbiX9RJHPT+vlTDE/tshIgfDu17E6A5Qz4y+AEs6S2dbWYzRHF6A0qz/P9SkNAwvKLB0siVX5fNSLPpWA8FrusS4aQXu//7r9O8//5N+vlmXOXpurbyLdjUaRmqYapvHFLydrvbNutqrGi0ahscUmCfJ3/rpZP2r2dUkvyla1zbaq7RZ+X35u7r1Kv1embRv+SprZ7+I3MtFmmpli70oxstxGQ1fQh621lISNoY82MYsvnbyTb1kol1lTrk1Z7pSy5Um+VsOe46qWO3o3p3evptcpp8Yq7t+b/yLn7Bq5aPcdkrNkhV9HRY/v9yLP0wOG5X7iErta1LOkrio+m5xekyzPaFUA1KzTC3IMD6qk6IfUzXa5jE+z9aS1KRHldeQdrSsx3J985SCLTmJd1KimFlMMvVIsZ1tVtxNmtTMR3UST5CVv4um5FjSEH7PV/MbraKhBFw6Y1XeelST0uuUHNY4Btj+vo719tHlGW6P82UZj+0xttRJ8RlpFO7k6yjPn5bpeJ3kbrfadtx+8pqGPPzHdLPPwHgsKiuOaB7LoZ0T1vKT13xbtLXv7N211knaqWFpVt/2N+sk7nXz88qCgL93p52iHaO1TtKrDa0aMPqkjtnRfPou7hbU192gmfpMolJ6nuSMdZ0kxiWEM/XWShCylJIWXrSUoVnDsT0HpySq4AtG9SRpheuwxJFS+6qL06I+IfDs9XGdFItgHvq5Yn3RV7f2G6veb2tS6U/wK7DNqzcdaggKZmc+SEQ+GVHKEfXdZsXr8lpOvio7uY6KeGsG3d80rv0qeWCJBmJBNdVJm/dqm5nHz5PS24PUOapA4mGuSXYn31J9W7Lb0uyP/OcTTVLqD9ahtnVeWV0PTFreXV7aoEnxP0v8pXpwvb3U86S3ujWc1vw4LNLJtD2cEohDKZb9YEE1Tze2ED/m3yTChkVVCM3/+L2SpEnFp53jOu2fDtjrwzppGyZNDG1N+oKvxj5v8XFY9SlNz//K3h07nJDJONsiG57WDoG6/+kqXFoFDbmIGeZUl4srjiR/IsHirsW0M67KfB7DayxjO70OuMS+ur2MWwzUmbWcb7dOIvjXFMWxZeOVsdoltOXZeqbAuk3XjqdJ8+1xHpbPLuUmjmuSHFUJi5v36Cm8NEz9MB+qf8dBOb34FK1OyqZl1XpYzsMz3xdiaXvVhzDcj+7bRk8Kw30MWg6r9i3NUhhIvNOjreVJ6Wr7O4e8JL1Bu7pNL3G0apJhrw80iaeE+SarpUnf8NUtdtMjELmqjTMGctT/s2sO/MDckoQwPKa5eE4OTOSsyLjjalrw4L86F97EzKdz0OzzdlAm/UznJWlo2cHSM1YBZFTk20UDPhz6F2XvLs7nUF/Rbq6TjtxudVMckuft5w3UK+wLok41GZbkxrYmkfL3B2H5qCYZq2L/1pN0F5JubC0c0aQGc2Z3T8WQOGshF/z8m2DlvnVc86wWsYyqn7qzT2dk4c8iSD1Yq06S81/1k0+4nKg4z7Q/YTnHi1iVEeUunBYZPz1PUqexvnenfdEie/t1X5VD2NekdO5YblgdTHX1/nh10mu6rVbVu5V3bKU01Un1AC27v43u6VNEvmGIs7RfJxEX5bcnlNq3Pdoer5PKJoRmelkt1Q6m5HlqZpaToVr/lK+jzHXKKaOQ3ahPys1VYFWE9Bu+n9y+a9Qk6t/qh2Dm5r4xwjStTXt3dm1halLqMDEPvfwdv79j5/mmGTanWcd0ECVHp9RJmgCwPUAl2a9nj51bunVSbsr2CVWTSE+29svOmPRdvlPs1UmN9rLqJMX79z95Lv/6dV+lznl5Bl+T4iyR1ITtazV8S6c78+U5h8W6xGgcWZHi8rKMsipqr5PYPfIf10l0hkti6mqS9CWRGzFRbD9Pmp/jXp0kh1Du39Ljmdbv0s7Dqm0gkxlj1aS4QHEvlzLMK/tCsyunql9Xvk3Wsz1xqqqnLLmHvsiZF3YEDZq0Bc3b0rgb3rLO07ajEraUt7fWSeUuON24MD+/j9WocZ7krJBdTdLdWlkwylcj2pco9h0H7jd6Wlfa2fv2kORfVJPyd1Rp+bF7EJ/ba/eouSyhVk36BV8le5tlOahpuLxsrbhfdRztWYf/KpWz9nnSNlHGYeSHhVocVLyr5tk9+48ZkStVCKl8NPbulLt8+qzuDlPz8zNJXAzxqP6YFwiJ5lJNKwdgDibTF/bhoxXxvdqUeEil2a85bUTptREJfUqQjJ9aN7iNnvzltUPPEUlxbDfYdBdcHlSo5FFVSauXzfmboc5JnZWJN6yT6kP3nd0k+jy9fmNlQ08eFzxvq/HugrMFnK/80rfzb3utb4O2uV3rfmpbc9tOYMv/i8wxezlZ7UnMmO7HpNksXV/3VeWljedJ7/YLe427hTSKld4KI2pfghPGsP8BMvGQI3Y/VieV0s2tk47MqnJAoBiUKseBOonvEybf4zdytXNlsVds3LCn1a1c2vVgi+fH2zdV1Kq2/fNZox6O6AplkcG9i2F8E610Nddt59M36iQAwK9y4DYUAP9woEkAAAB6AZoEAACgF6BJAAAAegGaBAAAoBegSQAAAHoBmgQAAKAXoEkAAAB6AZoEAACgF6BJAAAAegGaBAAAoBegSQAAAHoBmgQAAKAXoEkAAAB6AZoEAACgF6BJAAAAegGaBAAAoBegSQAAAHoBmgQAAKAXoEkAAAB6AZoEAACgF/4G/i1eDWASQBUAAAAASUVORK5CYII=" alt="" />

改进后算法如下:

class Solution {
public:
bool Find(vector<vector<int> > array, int target) {
int row = array.size();
int col = ;
int totalcol = array[].size();
if ( == row)
return ;
row--;
while (row >= && col<totalcol)
{
if (target < array[row][col])
row--;
else if (target > array[row][col])
col++;
else
return ;
}
return ;
}
};

运行通过:

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAcMAAACeCAIAAADBg/YUAAALdUlEQVR4nO3dW2sT3R6A8ffT9kMEL4SCSaF1eGlTpbEIycWmUpudu5TSSApa3IIpDcUDIga1AYsiNUSt1O6LSWbWWrPWHPrvKZnnd9XMTGamXjyuOXTmnzMAgMw/170DADDxKCkASFFSAJCipAAgRUkBQIqSAoAUJQUAKUoKAFKUFACkKCkASFFSAJCipMjmz58/w+HwuvcCuFkoKUKnp6eJyzSbzYWFhSvYGWCCUFKMHB4eep53fHwcv1ij0Zidnb2aXQImBSVFqN1u//vvv4PBIDrr9+/fz549a7fb9+/fv337drvd3tnZ+fLly9XvJHADUVJotre3FxcXozHt9Xq3IjY3N69lJ4GbhpLCtLW1tbS0FL2s9PPnz+FwuLGxMTs7OxwOh8NhmvOqQB5QUpydnJy8evVqc3OzVqstLS0tLCwsLCysra1ZF+Y8KRBFSXOt3+8/fvx4dnZ2dXW11WodHBx8/vx5d3e3WCweHh5av7K3t1ev1694P4EbjpLm1PHx8dra2tzcXLvdVs+Kvn379s6dO58+fbrGfQMmDiXNo4ODg2KxuLW19evXL3X6u3fvSqXSx48fr2vHgAlFSXPnyZMn8/Pz0VHn0dFRsVj88OHDtewVMNEoab741+V//PgRnXVycvL169er3yVgClDSHHnx4oXrxvtAr9f7n+79+/dXtofAhKKkedHv94vF4tHRUfxilUpldXX1P2MPHz5cXFy8mj0EJhclzYXT09Pl5eWXL18mLrmysqKeKu33+ylL2q0VZmZmZrxmMKXpGRPs/MUSlmt6wSKjDRVqXeeiznmuHXdtPGlbwa5l2ySmDyXNhU6nU6lU0ix5ySUdLZWKEieltglxGy054zXDn+38HRst41idvKSWX9irOf4REv/Twc1FSaff379/Pc9LeVE+c0njc5WiEynGpNGQ2oxiNl5i9LHpqZ0Lvh6WL66WF1XS0S+nfYh8xCSjpNPv3bt39+7dS7nw5R/dp0xv+L1x/cJhprlOI2bdWiH8udscl7VQcCS92+2enXWbzVrCniWPc6O/gW1M2tR2m5JOBUo6/TY2NnZ3d1MufPXnSVOueMZrattQfnaNCtMc3afatntMqoYyZlRrjEmtA2vOtE40Sjr95ubmvn37lnLhKyhpmnOlYVaCHHpNrZjh9qJbtuyAWrS4xDc9dUZCSc3fxLJK65jUPKzXz0BgElHSKTcYDObn542JxWLR9aTRjCXNcLBrjMxcY0J9gKmsf3SWdPw161rCbhVq3RRjUqVz6kfztKo9cv7M0UmDQq0W3l6QRBubFmpdSjr5KOn0M/64/uzs7NatW+rHvb29RqPh/3zuMal60VydEA1EhjGpuuhoxeMBZVBSc4Q5ClxQ0qQxqZZko6UxJTW2X6h1ww0n/Kqji/eUdJpQ0jy68JI6qhlzi5F6GSlm6aYXjPrUCgbdUpOqrfmcJVXiF3vLlXI3gTqIdp830GLJmHT6UNI8utCSGgE0YzIeqxZq3Wy3k/praTbVVCplc54nNUsas3JleX1QqyfPjJw+/NZPR5gD03E0bSUdD005TzoFKGkeXVhJg2yGYzR1UjhDj1c2kWaqUVb6qp2GPfeY1LZpNXLKFTB1gv3PCIyS+iLngLkPagpQ0uk0HA4bjcZ/dcFj8C/66F5th5ZO9SjcXDpe9AK6cRyvfrC062JKalYyPCfhHl3rR/zjFheMc6jmPwIj0glHSadTv9+/e/eu+kinBw8ePH/+3J97oSU1zniOMxXGxPwjplR/Xmktabfm2e8A8P8sv9btniWU1AsCZpxXdac+qXHxv475H4s2xf9SGGUGp5OLkk6nfr+/srKiTmk0GpdRUscle+30pXGMfO6SJiyn71DaLhn3WWUX++sYB/dqOrWtZX3sCm4aSjqdrqyk+t9mRk9f+gPFphcMGQVH99pm7QELr92kuLilXTVPt7zl948tqfIMq+RN0NIJRkmnU7/fX15e/qp49OiRWlJ11tOnT9WS7u/vB7PevHmT9vmklmsqcQuef0waM4rsNr1ClpFl1uVt4n6dbtMrEMhcoKTT6fv3757nLehev37tz11eXjZm7ezs+LPq9boxy/XiewABSgoAUpQUAKQoKQBIUVIAkKKkACBFSQFAipICgBQlBQApSgoAUpQUAKQoKQBIUVIAkKKkACBFSQFAipICgBQlBQApSgoAUpQUAKQoKQBIUVIAkKKkACBFSQFAipICgBQlBQCphJIOAACxKCkASFFSAJCipAAgRUkBQIqSAoAUJQUAKUoKAFKUFACkKCkASFFSAJCipAAgRUkBQIqSAoAUJQUAKUoKAFKUFACkKCkASFFSAJCipAAgRUkBQIqSAoAUJQUAKUoKAFKUFACkKCkASFFSAJCipEijVS1VW+HPNuX6vvKF/Xq5VG05Fg5WFbtBdYX79fL4c6rNA1eLkiIdI22JCyfmUi+iuW7L5mL2YL9ePkdJe9uV0dYr272sXwZUlBRppczVfr2cddSZlE11RCzZNVVvu1IqrXcGg8Fg0FknppChpMjEcWwdjCuD6CXGzSxp3X3Urq7UeqLAtbH9etlx3N/brqjx7KyPPvnTt9dHq1/vDDrKz8FXGctCR0mRbJxPtUnxB/D+3Gj4lD6eZ0xqFDMx2+6SBun09bYrfin9TPrR9Bvq/xyUt7MeNlX9GflGSZGSXqugdJYjb+XykEZfNHKedHyRSl+/9sWsY1InY0gaflYP+q3VpJ6woaRISa2V8bMlkKlKao5JlVVdzJjUKbakwQx14BoUNDy4J6gIUFKkpNTKGIfqAay2XGFLLKmyzCWXNPboPr6k4Qo4VYoAJUVKQa3sF52Muz/PW1LL3Ms4ug/T6TOuOKUoabAWUooBJUVq47a1qraD91ZVmZS2pI4Qq1vTvxhzZSnjFSfXXVCJJVWLSkgxRkmRQqtaKpWq9ZR3il7emDRm/7KWdGC/Mz/FmDS4LYpTpQhQUiRTShZ3P2mwUOQyv7lA3JYso1RXSe1LA1ePkgKAFCUFAClKCgBSlBQApCgpAEhRUgCQoqQAIEVJAUCKkgKAFCUFAClKCgBSlBQApCgpAEhRUiQw3i5iiH02VMxDmhIflJe4ZeAGoaRIkFhSZaa5rOu5oelK6v72eSiPFVWfKqq8c1l7Uqlruv3xpLwnL+8oKRLYX7Vsf6WTu6TuFzbrzy5NHONqS6emPiFff9J9Z92eQPt05en62kopad5RUiS4mKN7Yy2W5BrbyH5o7z/Y3/4VrXTqO5yyh9R4LZ7fVWWGP5glqzlDSZHgYo7uo+9y1g7cIyVtVUvlessxkLXvTlxJXWPS3nalUgkO47WXkFinR9eql1TdDvKEksIifqRpfVHyYDBIX1J//XpZU5xfjXwtk+AEp/5OUaOf/gfXdJX5Tr31jv4t5AklhUXMtZ7oK+czH923qqVStaWNIbWS2gaX8e+2S6Q1zn1S0zUnOt0YfAaVJqQ5RUlhkbqkRleTx6T6O56DPoYl3a+XS+VyefQmU6dsA1P1JaGDmLcrq2dQ3dN72xUzmco7nGlpLlFSWKQuqXFUnuLafSSBrWqpXK+P1uOv3XJqVnZvqaukritIzitL5nG/soD/BWekMd0oKSzSltR8sX3qK06WDcacbk3+/mgdsdfutaP70Qd9sBkG0zHd2UklvZwszSVKCouUV5wiwb2xJR1od9Rrocsw3bhb37feGRiDWFqaQ5QUFunGpO6bQMMSj5e1l1C5X991kiBcFX84ipuLkgKAFCUFAClKCgBSlBQApCgpAEhRUgCQoqQAIEVJAUCKkgKAFCUFAClKCgBSlBQApCgpAEhRUgCQoqQAIEVJAUCKkgKAFCUFAClKCgBSlBQApCgpAEhRUgCQoqQAIEVJAUCKkgKAFCUFAKnkkgIAEv0fXFHQCIWSIIgAAAAASUVORK5CYII=" alt="" />