图解一道今日头条面试算法题 ﹏ヽ暗。殇╰゛Y 2022-12-31 03:27 124阅读 0赞 前几天听同事分享了一道今日头条的算法面试题，感觉非常有趣，今天也分享给大家，题目是这样的： 给定一个有序数组，数组中有正数、负数或者0，对数组中所有的数求平方后问有多少个不同的值。 比如对于数组\[-1,0,1,1,1,1\]，对数组求平方后为\[1,0,1,1,1,1\]，那么最终的结果是2，因为最后只有0和1两个不同的数； 对于数组\[-1,0,1,2,3\]，对数组求平方后为\[1,0,1,4,9\]，那么最终的结果是4，因为最后数组中为0,1,4,9这四个不同的数； 同事提到只有时间复杂度为O(n)，空间复杂度为O(1)的算法才能通过面试，在听到这个题目后首先想的就是如果在面试中自己遇到这个题目该如何解决？ #### 我是如何思考的 #### 如果在面试中遇到这个题目我会先给出一个最简单的解法，也就是直接对数组中的每一个数字求平方，然后放到map中，最后求一下map的大小就可以了，整个过程如图所示： ![format_png][] 实际上这种解法有个问题，那就是对数字求平方和容易导致**溢出**，而实际上我们根本就无需求平方，实际上只需要求出**绝对值**就可以了，只要两个数字的绝对值相等，那么这两个数字的平方也一定相等。因此我们只需要将上图中的第一步由求平方改为求绝对值就可以了。 这个算法相对简单，也很容易想到，实际复杂度为O(n)满足要求，但是由于我们使用了map，因此空间复杂度为O(n)，不能满足面试要求的O(1)，那么该如何改进呢？ 在往下看之前你要首先自己想一想该如何改进。 #### 优化算法：利用数组有序 #### 不要忘了题目给定的是一个**有序**数组，上图中的算法没有利用到这一性质。 我的想法是这样的，给定一个有序数组，如果这个数组中没有负数，那么这个题目是极其简单的，因为在一个有序数组中相同的数组**一定是相邻的**。 比如对于数组\[0,1,1,1,1\]，其中四个1是相邻的，我们只需要在遍历数组的时候不计入重复的数字就可以了。 但是现在问题的关键在于数组中还有负数，对于负数该如何处理呢？很简单，我们只需要将负数部分转为正数就可以了，这样我们就得到了两个子数组，这两个子数组都是有序的，然后将这两个有序子数组原地合并，这样就得到了一个不包含负数的有序数组，问题圆满解决，如图所示： ![format_png 1][] #### 问题 #### 看上去看正确有没有，没有额外使用空间，而且时间复杂度是O(n)，但是，这里有一个问题，这个问题出在了上图中的第4步，也就是原地合并数组中的两个部分，当时思考的时候没有意识到，那就是**没有办法在不借助额外内存空间的情况下合并两个有序子数组**，至少我没有想到这样的方法，如果你想到了请务必在公众号后台留言指正。 #### 再次思考 #### 发现这个问题后上面的解法从第4步之后都是不正确的了，但是我直觉这个解法距离正确答案应该不远了，既然我们没有办法在不借助外部空间的情况下合并两个有序子数组，那么**真的有必要去合并两个子数组吗**，意识到这一点后，惊喜的发现在不进行合并的情况下问题能够解决，只需要设置两个指针i和j，分别指向两段数组的起始位置，设置num用来记录最后结果，在上图第3步逆转顺序后如图所示： ![format_png 2][] 聪明的你看到上图就能明白这个算法了。 顺便说一句，双指针是数组类算法题中非常常见的解题思路。 #### 进一步优化 #### 在想到双指针可以解决这个问题后我进一步意识到其实根本没有必要找到是负数的那一部分子数组然后取反再逆转，实际上这些都没有必要，我们只需要比较数组中两个数字的绝对值就可以了，有的同学可能会说那逆转数组也没有必要吗，是的，没有必要，上图中两个指针是相同方向前进，在不逆转负数那一部分数组的情况下，只需要两个指针逆向前进就可以了，如图所示： ![format_png 3][] 这样我们最终得到了一个很简单很容易编写代码的解决方法。 有了以上分析，代码就非常简单了。 #### 代码实现 #### int Solution(vector<int>& arr) { if (arr.size() == 0) return 0; int i = 0; int j = arr.size() - 1; int num = 0; while(i <= j) { ++num; if (abs(arr[i]) > abs(arr[j])) { ++i; while(i <= j && arr[i-1] == arr[i]) ++i; } else if (abs(arr[i]) < abs(arr[j])) { --j; while(i<= j && arr[j]==arr[j+1]){ --j; } } else { ++i;--j; while(i <= j && arr[i-1] == arr[i]) ++i; while(i<= j && arr[j]==arr[j+1]) --j; } } return num; } 代码非常简单，唯一需要注意的地方在于下标的移动。 #### 总结 #### 在这里详细的讲述了我对这道题目的思考过程，从这里也可以看到，除了提前见过这个题目，否则有时我们可能没有办法一下就想到最优解，要想找到最优解你需要不断的尝试验证，这个过程是非常有必要的，有很多同学可能学过很多关于数据结构和算法的资料但是始终不得要领，很关键的一点就是思考过程是作者的而不是你的，没有什么东西是轻而易举就能学会的，除非其真的很简单，**但是，数据结构与算法并不属于这一类**。 -------------------- **为你推荐** <table> <tbody> <tr> <td>1，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb986d1cbce0fc753efd9fef7497f1788c981f1769097754a7cdeeb8a9cb5c250d14166a215&idx=2&mid=2247483791&scene=21&sn=456e78baeea0f6cec222c0feea236863#wechat_redirect" rel="nofollow">彻底理解二叉树的遍历</a></td> </tr> <tr> <td colspan="1">2，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98621cbce0f379a61fd68f64bed3e8e2d244235231786e908e7e0682cf349cda98edac7d0&idx=1&mid=2247483775&scene=21&sn=4dba79d9b015123ba58903086c9add60#wechat_redirect" rel="nofollow">彻底理解堆</a><br></td> </tr> <tr> <td colspan="1">3，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&idx=1&mid=2247483951&scene=21&sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">经典算法题：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&idx=1&mid=2247483951&scene=21&sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">两个有序数组中位数</a></td> </tr> <tr> <td colspan="1">4，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98603cbce0f151539b4123bc354c229ad911df4053b0cd72a805806486740892efc998259&idx=1&mid=2247483741&scene=21&sn=faf6b1e9e064389336546e7dcd555fd1#wechat_redirect" rel="nofollow">送命题：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98603cbce0f151539b4123bc354c229ad911df4053b0cd72a805806486740892efc998259&idx=1&mid=2247483741&scene=21&sn=faf6b1e9e064389336546e7dcd555fd1#wechat_redirect" rel="nofollow">进程切换与线程切换的区别</a><br></td> </tr> <tr> <td colspan="1">5，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98548cbce0c5e054f9b90cd4004ff5d94b4ffedd87c86716b97de5aadcacf2de8dd4883b2&idx=1&mid=2247483926&scene=21&sn=a5f0097a10385a2ca6be8b9d1903e1b5#wechat_redirect" rel="nofollow">一道决定面试成败的算法题</a><br></td> </tr> <tr> <td colspan="1">6，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb9851acbce0c0c09086ab6f014441a0376ccf468ae988d99013c91da6469e534b58845e7d7&idx=1&mid=2247483972&scene=21&sn=bfac0711c3bfe415ef9809c796ea2f2d#wechat_redirect" rel="nofollow">LeetCode：二叉树最低公共祖先</a><br></td> </tr> <tr> <td colspan="1">7，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98552cbce0c44953d79c8d0943aab40aeb9098eeffe533537ac9d23d17922b1826f83465c&idx=1&mid=2247483916&scene=21&sn=89851d1f4a6f53ed0308cd4a4da5881e#wechat_redirect" rel="nofollow"></a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb9856bcbce0c7de355c30b9b89ff7a56250324caa5b19f57e6423d6685c36707856c410798&idx=1&mid=2247483957&scene=21&sn=2637a7757351a3e8da0ae8a27488d295#wechat_redirect" rel="nofollow"></a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&idx=1&mid=2247483951&scene=21&sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">LeetCode：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&idx=1&mid=2247483951&scene=21&sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow">两个有序数组的中位数</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb9856bcbce0c7de355c30b9b89ff7a56250324caa5b19f57e6423d6685c36707856c410798&idx=1&mid=2247483957&scene=21&sn=2637a7757351a3e8da0ae8a27488d295#wechat_redirect" rel="nofollow"></a><br></td> </tr> <tr> <td colspan="1">8，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&idx=1&mid=2247483951&scene=21&sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow"></a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb9856bcbce0c7de355c30b9b89ff7a56250324caa5b19f57e6423d6685c36707856c410798&idx=1&mid=2247483957&scene=21&sn=2637a7757351a3e8da0ae8a27488d295#wechat_redirect" rel="nofollow">LeetCode：</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb9856bcbce0c7de355c30b9b89ff7a56250324caa5b19f57e6423d6685c36707856c410798&idx=1&mid=2247483957&scene=21&sn=2637a7757351a3e8da0ae8a27488d295#wechat_redirect" rel="nofollow">堆叠字符串</a><a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb98571cbce0c67abbced92c9b5eeacb59bdb44bab631fe73651105169ec7df571f4e59185d&idx=1&mid=2247483951&scene=21&sn=25ec562d60179985cba531dd8b06ae77#wechat_redirect" rel="nofollow"></a><br></td> </tr> <tr> <td colspan="1">9，<a href="http://mp.weixin.qq.com/s?__biz=MzU2NTYyOTQ4OQ%3D%3D&chksm=fcb986a0cbce0fb64a2242783b4f52da4a1c141d606a3433f6a8e2584f59d10c76e7c41d5239&idx=1&mid=2247483902&scene=21&sn=4956ffd8d89934e8ec2c3e3e5f8ccb8b#wechat_redirect" rel="nofollow">一个耗时4小时的内存泄漏问题</a><br></td> </tr> </tbody> </table> ![format_png 4][] PS：微信公众号从去年开始限制了留言功能，如果你有任何问题欢迎直接在公众号留言。 [format_png]: /images/20221120/c2149c19d817483bb61f590e520d42b6.png [format_png 1]: /images/20221120/99d96959515a4be3aaf7a3ce894f7eda.png [format_png 2]: /images/20221120/4ac1b603f95240278a3d75f5c4bd293e.png [format_png 3]: /images/20221120/a8888eab2075487b8a1cf7bca8962130.png [format_png 4]: /images/20221120/c33437fa98f54f61baa223fcdb92cf8f.png
还没有评论，来说两句吧...