<p><img src="https://img.haomeiwen.com/i1940317/7f0e4f729f489bc5" /></p><p ><img class="" data-copyright="0" data-ratio="0.4255555555555556" data-s="300,640" src="https://img.haomeiwen.com/i1940317/d7da7d46e10922f9" data-type="jpeg" data-w="900" ></p><section class="output_wrapper" ><h3 ><span >题目描述</span></h3><p >在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。</p><h3 ><span >题目分析</span></h3><figure ><img class="" data-ratio="0.5261239368165249" src="https://img.haomeiwen.com/i1940317/c57dc22c2a20abbe" data-type="jpeg" data-w="1646" title="图 1"><figcaption >图 1</figcaption></figure><p >如果没有头绪的话，很显然使用 <strong >暴力解法</strong> 是完全可以解决该问题的。</p><p >即遍历二维数组中的每一个元素，时间复杂度：O(n^2)。</p><p >其实到这里我们就可以发现，使用这种暴力解法并没有充分利用题目给出的信息。这个二维数组是有特点的。</p><ul class=" list-paddingleft-2"><li><p>每一行都是<strong >递增</strong>的</p></li><li><p>每一列都是<strong >递增</strong>的</p></li></ul><figure ><img class="" data-ratio="0.5436766623207301" src="https://img.haomeiwen.com/i1940317/988f35faa2943861" data-type="jpeg" data-w="1534" title="图 2"><figcaption >图 2</figcaption></figure><h3 ><span >解法</span></h3><h3 ><span >解法一：二分法</span></h3><p >对于有序数组的查找问题而言，<strong >二分法</strong>是最容易想到的一个解法。</p><p >在这里，对每一行使用二分查找，时间复杂度为 O(nlogn) 。二分查找复杂度 O(logn)，一共 n 行，所以是总体的时间复杂度是 O(nlogn) 。</p><h3 ><span >解法二：规律法</span></h3><p >根据二维数组由上到下，由左到右递增的规律。</p><p >从左下角开始遍历，如果当前值比 target 小则往右找，如果比 target 大则往上找，如果存在，必然可以找到目标数字。</p><p >即选取右上角或者左下角的元素 a[row] [col] 与 target 进行比较， 当target小于元素 a[row] [col] 时，那么 target 必定在元素 a 所在行的左边,让 col-- ；当 target 大于元素 a[row] [col] 时，那么 target 必定在元素 a 所在列的下边,让 row++ ；</p><figure ><img class="" data-ratio="0.5049382716049383" src="https://img.haomeiwen.com/i1940317/a8d41300dbd21bfe" data-type="jpeg" data-w="1620" title="图 3"><figcaption >图 3</figcaption></figure><p >代码如下：</p><pre ><code class="java language-java hljs" ><span class="hljs-keyword" >public</span> <span class="hljs-class" ><span class="hljs-keyword" >class</span> <span class="hljs-title" >Solution</span> </span>{<br /> <span class="hljs-function" ><span class="hljs-keyword" >public</span> <span class="hljs-keyword" >boolean</span> <span class="hljs-title" >Find</span><span class="hljs-params" >(<span class="hljs-keyword" >int</span> target, <span class="hljs-keyword" >int</span> [][] array)</span> </span>{<br /> <span class="hljs-keyword" >int</span> row = <span class="hljs-number" >0</span>;<br /> <span class="hljs-keyword" >int</span> col = array[<span class="hljs-number" >0</span>].length - <span class="hljs-number" >1</span>;<br /> <span class="hljs-keyword" >while</span>(row <= array.length - <span class="hljs-number" >1</span> && col >= <span class="hljs-number" >0</span>){<br /> <span class="hljs-keyword" >if</span>(target == array[row][col])<br /> <span class="hljs-keyword" >return</span> <span class="hljs-keyword" >true</span>;<br /> <span class="hljs-keyword" >else</span> <span class="hljs-keyword" >if</span>(target > array[row][col])<br /> row++ ;<br /> <span class="hljs-keyword" >else</span><br /> col-- ;<br /> }<br /> <span class="hljs-keyword" >return</span> <span class="hljs-keyword" >false</span>;<br /> }<br />}<br /></code></pre><h3 ><span >解法三：二分规律法</span></h3><p >将解法一和解法二进行结合：<strong >对每行每列都使用二分查找，此时的时间复杂度为 O(logn * logm)</strong>。</p><figure ><img class="" data-ratio="0.5529953917050692" src="https://img.haomeiwen.com/i1940317/3c9bf64f49487d15" data-type="jpeg" data-w="1953" title="图 4"><figcaption >图 4</figcaption></figure><p >比如查找数字 9，首先使用用二分查找选出一行，总共有 5 行，那么<code >( 0 + 5 ) / 2 = 2</code>，所以我们找出了第 2行为基准行。</p><figure ><img class="" data-ratio="0.5521472392638037" src="https://img.haomeiwen.com/i1940317/48f3f90f44f86b61" data-type="jpeg" data-w="1956" title="图 5"><figcaption >图 5</figcaption></figure><p >接下来对这一行（即第 2 行）又使用二分查找， 找出这一行（即第 2 行）中最后一个比目标值小的值，这里是 6。</p><figure ><img class="" data-ratio="0.5619146722164412" src="https://img.haomeiwen.com/i1940317/29c23e65e9ce6642" data-type="jpeg" data-w="1922" title="图 6"><figcaption >图 6</figcaption></figure><p ><strong >6</strong> 及其所在的行和列把这个矩形划分为 <strong >4</strong> 部分：</p><figure ><img class="" data-ratio="0.5558414822439527" src="https://img.haomeiwen.com/i1940317/af14b6e602e684a9" data-type="jpeg" data-w="1943" title="图 7"><figcaption >图 7</figcaption></figure><ol class=" list-paddingleft-2"><li><p><strong >左上部分（图 7 灰色部分）</strong>，包括所在行的左边部分和所在列的上边部分：这一部分是绝对不会有目标数字的。因为这部分数字肯定比 6 小，而 6 又是小于目标数字的，所以左上部分全部小于目标数字。也就是说这个区域的数字不需要再进行判断了。</p></li><li><p><strong >右下部分（图 7 绿色部分）</strong>，包括所在行的右边部分，但不包括所在列的下面部分， 这一部分也是绝对不会有目标数字的。因为这部分都比 6 右边的数字 11 大，而 11 又比目标数字 9 更大，所以右下部分全部都比目标数字大。也就是说这个区域的数字也不需要再进行判断了。</p></li><li><p><strong >左下部分（图 7 蓝色部分）</strong>，可能含有目标数字。</p></li><li><p><strong >右上部分（图 7 棕色部分）</strong>，可能含有目标数字。</p></li></ol><p >这样，实际上筛选的区域就只剩下<strong >左下部分（图 7 蓝色部分）</strong>和 <strong >右上部分（图 7 棕色部分）</strong>这两块区域了，相比于解法二而言，使用这种解法<strong >平均情况下每一次查找，都可以把行和列的长度减少一半</strong>。</p><p >代码如下：</p><pre ><code class="java language-java hljs" ><span class="hljs-keyword" >public</span> <span class="hljs-class" ><span class="hljs-keyword" >class</span> <span class="hljs-title" >Solution</span> </span>{<br /> <span class="hljs-function" ><span class="hljs-keyword" >public</span> <span class="hljs-keyword" >boolean</span> <span class="hljs-title" >Find</span><span class="hljs-params" >(<span class="hljs-keyword" >int</span> target, <span class="hljs-keyword" >int</span> [][] array)</span> </span>{<br /> <span class="hljs-comment" >// 特殊情况处理</span><br /> <span class="hljs-keyword" >if</span> (array == <span class="hljs-keyword" >null</span> || array.length == <span class="hljs-number" >0</span> || array[<span class="hljs-number" >0</span>].length == <span class="hljs-number" >0</span>) {<br /> <span class="hljs-keyword" >return</span> <span class="hljs-keyword" >false</span>;<br /> }<br /><br /> <span class="hljs-keyword" >int</span> h = array.length - <span class="hljs-number" >1</span>;<br /> <span class="hljs-keyword" >int</span> w = array[<span class="hljs-number" >0</span>].length - <span class="hljs-number" >1</span>;<br /><br /> <span class="hljs-comment" >// 如果目标值小于最小值 或者 目标值大于最大值，那肯定不存在</span><br /> <span class="hljs-keyword" >if</span> (array[<span class="hljs-number" >0</span>][<span class="hljs-number" >0</span>] > target || array[h][w] < target) {<br /> <span class="hljs-keyword" >return</span> <span class="hljs-keyword" >false</span>;<br /> }<br /> <span class="hljs-keyword" >return</span> binarySearchIn2DArray(array, target, <span class="hljs-number" >0</span>, h, <span class="hljs-number" >0</span>, w);<br /> }<br /><br /><br /> <span class="hljs-function" ><span class="hljs-keyword" >public</span> <span class="hljs-keyword" >static</span> <span class="hljs-keyword" >boolean</span> <span class="hljs-title" >binarySearchIn2DArray</span><span class="hljs-params" >(<span class="hljs-keyword" >int</span>[][] array, <span class="hljs-keyword" >int</span> target, <span class="hljs-keyword" >int</span> startX, <span class="hljs-keyword" >int</span> endX, <span class="hljs-keyword" >int</span> startY, <span class="hljs-keyword" >int</span> endY)</span> </span>{<br /> <span class="hljs-keyword" >if</span> (startX > endX || startY > endY) {<br /> <span class="hljs-keyword" >return</span> <span class="hljs-keyword" >false</span>;<br /> }<br /> <span class="hljs-comment" >//首先，根据二分法找出中间行</span><br /> <span class="hljs-keyword" >int</span> x = (startX + endX) / <span class="hljs-number" >2</span>;<br /> <span class="hljs-comment" >//对该行进行二分查找</span><br /> <span class="hljs-keyword" >int</span> result = binarySearch(array[x], target, startY, endY);<br /> <span class="hljs-comment" >//找到的值位于 x 行，result 列</span><br /> <span class="hljs-keyword" >if</span> (array[x][result] == target) {<br /> <span class="hljs-keyword" >return</span> <span class="hljs-keyword" >true</span>; <span class="hljs-comment" >// 如果找到则成功</span><br /> }<br /> <span class="hljs-comment" >//对剩余的两部分分别进行递归查找</span><br /> <span class="hljs-keyword" >return</span> binarySearchIn2DArray(array, target, startX, x - <span class="hljs-number" >1</span>, result + <span class="hljs-number" >1</span>, endY)<br /> || binarySearchIn2DArray(array, target, x + <span class="hljs-number" >1</span>, endX, startY, result);<br /> }<br /><br /> <span class="hljs-function" ><span class="hljs-keyword" >public</span> <span class="hljs-keyword" >static</span> <span class="hljs-keyword" >int</span> <span class="hljs-title" >binarySearch</span><span class="hljs-params" >(<span class="hljs-keyword" >int</span>[] array, <span class="hljs-keyword" >int</span> target, <span class="hljs-keyword" >int</span> start, <span class="hljs-keyword" >int</span> end)</span> </span>{<br /> <span class="hljs-keyword" >int</span> i = (start + end) / <span class="hljs-number" >2</span>;<br /> <span class="hljs-keyword" >if</span> (array[i] == target || start > end) { <br /> <span class="hljs-keyword" >return</span> i;<br /> } <span class="hljs-keyword" >else</span> <span class="hljs-keyword" >if</span> (array[i] > target) {<br /> <span class="hljs-keyword" >return</span> binarySearch(array, target, start, i - <span class="hljs-number" >1</span>);<br /> } <span class="hljs-keyword" >else</span> {<br /> <span class="hljs-keyword" >return</span> binarySearch(array, target, i + <span class="hljs-number" >1</span>, end);<br /> }<br /> }<br />}<br /></code></pre></section><p><br /></p><h3 ><span >End</span></h3><p ><strong >今日问题：</strong></p><p >不知不觉「五分钟学算法」已更新了快百篇原创，坚持原创日更很长一段时间了。所以，你希望接下来小吴更新哪方面的算法知识内容呢？留言区点赞前五名的都可获得小红包一个，<strong >小吴很期待你的建议</strong>~</p><p ><br /></p><p ><strong >打卡格式：</strong></p><p >打卡 X 天，答：xxx 。</p><p ><br /></p><p ><p><span class="js_jump_icon h5_image_link" data-positionback="static" ><img class="" data-copyright="0" data-ratio="0.3333333333333333" data-s="300,640" src="https://img.haomeiwen.com/i1940317/0b92bf5c44427f23" data-type="png" data-w="600" ></span></p></p><p ><strong > </strong><br /></p><section data-role="outer" label="Powered by 135editor.com" ><section data-role="outer" label="Powered by 135editor.com" ><section ><section class="" data-brushtype="text" ><span >喜欢就点击“好看”吧！</span></section></section></section></section>
网友评论