亲宝软件园·资讯

展开

「面试指南」JS数组Array常用算法,Array算法的一般解答思路

小小👨‍💻‍ 人气:0
#### 先看一道面试题 在 LeetCode 中有这么一道简单的数组算法题: ```javascript // 给定一个整数数组 nums 和一个目标值 target, // 请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。 // 你可以假设每种输入只会对应一个答案。 // 但是,你不能重复利用这个数组中同样的元素。 // 示例: // 给定 nums = [2, 7, 11, 15], target = 9; // 因为 nums[0] + nums[1] = 2 + 7 = 9, // 所以返回 [0, 1]。 ``` 对于上述的面试题,对于我们前端开发,不同的解法,有着不同的技术水准。 那么到底有几种常用解法?实践并汇总了以下几种方法: - 暴力双 for 循环解法; - 单循环 indexOf 优化; - 单循环 obj 优化; - 单循环 map 优化; - 单循环尾递归优化; #### 暴力双 for 循环破解 ```javascript // 两层循环判断,找出当前元素cur与target-cur的,满足放入result结果中 function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { const cur = nums[i]; for (let j = 0; j < nums.length; j++) { const others = nums[j]; // 因为是不可以重复利用同样的元素,所以i!==j; if (others == target - cur && i !== j) { // 因为是我们只找出一个结果,所以我们找到后,直接返回结果 return [i, j]; } } } // 如果未找到,返回[] return []; } // 测试结果 let result = twoSum([2, 7, 11, 15], 9); console.log(result); // [0,1] 2,7 满足结果,所以返回其下标[0,1] ``` 时间复杂度:O(n^2),可能看似感觉还不错,但是执行时间长,内存占用也不小,当 nums 数组足够大时,它的性能瓶颈就会体现出来。 leetCood 测试结果: ![csjg](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170138372-134872842.png) #### 单循环 indexOf 优化; ```javascript // 单循环判断,找出当前元素cur,与target-cur是否相等,满足放入result结果中 function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { let cur = nums[i], others = target - cur, // 期望目标值 others_index = nums.indexOf(others); // 判断期望目标值是否在nums中,因为不能是它本身,要校验两个下标不能相等 if (others_index > -1 && i !== others_index) { // 因为是我们只找出一个结果,所以我们找到后,直接返回结果 return [i, others_index]; } } // 如果未找到,返回[] return []; } // 测试结果 let result = twoSum([2, 7, 11, 15], 9); console.log(result); // [0,1] 2,7 满足结果,所以返回其下标[0,1] ``` 时间复杂度:O(n^2),因为 indexOf()方法的时间复杂度为 O(n),所以和上述暴力破解只是写法上区别了。执行时间,内存占用依然存在可优化的空间。 leetCood 测试结果: ![测试结果](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170206914-1472119450.png) #### 单循环 obj 优化: 使用 obj,边存边比较目标差值是否在 obj 中。如果存在,直接返回下标,不存在继续边存边比,直到结束循环; ```javascript function twoSum(nums, target) { let obj = {}; for (let i = 0; i < nums.length; i++) { if (obj[target - nums[i]] >= 0) { return [obj[target - nums[i]], i]; } obj[nums[i]] = i; } return []; } // 测试结果 let result = twoSum([2, 7, 11, 15], 9); console.log(result); // [0,1] 2,7 满足结果,所以返回其下标[0,1] ``` 时间复杂度:O(n),由于对象键值对 key-value 的优越性,对于作为查找类的算法很有优势。时间复杂度降为原有的一倍,性能会好一些。 leetCood 测试结果(较上优化了 90ms 左右): ![测试结果](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170228784-1872314201.png) #### 单循环 map 优化: 上述我们使用了一个对象作为查找的依据,同样的我们可以根据 map 替换,来破解。 ```javascript function twoSum(nums, target) { let map = new Map(); // 遍历nums 放入 map中 for (let i = 0; i < nums.length; i++) { let value = nums[i]; map.set(value, i); } for (let j = 0; j < nums.length - 1; j++) { if (map.has(target - nums[j]) && map.get(target - nums[j]) != j) { return [j, map.get(target - nums[j])]; } } // 不符合,返回空数组 return []; } // 测试结果 let result = twoSum([2, 7, 11, 15], 9); console.log(result); // [0,1] 2,7 满足结果,所以返回其下标[0,1] ``` 时间复杂度:O(2n),第一次循环时间度 n,第二次为 n\*1,故为 O(2n), 由于 map 的特殊数据结构,故作为查找类的算法,相比 obj 具有绝对优势。 leetCood 测试结果(较上再次优化了 近 30ms): ![测试结果](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170256232-321742534.png) #### obj 尾递归优化; 我们对于上面单循环 obj 做下改造,利用尾递归的方式破解: ```javascript var twoSum = function(nums, target, i = 0, objs = {}) { const obj = objs; //存在期望数字; // 判断obj中是否 if (obj[target - nums[i]] >= 0) { // 存在直接返回两值的下标; return [obj[target - nums[i]], i]; } else { // 不存在,存入obj obj[nums[i]] = i; // 递归继续查找 if (i < nums.length - 1) { // i 自增 i++; return twoSum(nums, target, i, obj); } else { // 递归结束,未查询到结果 return []; } } }; ``` 时间复杂度:O(n),假设我们查找到,则递归的次数应该是最多的为 n,所以时间复杂度 O(n); 递归相比于 for 循环是一种更近层次的查找,在树结构数据、多维数组中我们常用递归思想来处理数据。 leetCood 测试结果(结果为 52ms),多次执行测试大都在 60ms 上下,说明了递归思想的优势: ![测试结果](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170312381-117837714.png) #### map 尾递归优化破解; 我们同时对单循环 map 的也是用递归,看看会发生什么结果? ```javascript var twoSum = function(nums, target, i = 0, maps = new Map()) { const map = maps; // 判断obj中是否 if (map.has(target - nums[i])) { // 存在直接返回两值的下标; return [map.has(target - nums[i]), i]; } else { // 不存在,存入obj map.set([nums[i]], i); // 递归继续查找 if (i < nums.length - 1) { // i 自增 i++; return twoSum(nums, target, i, map); } else { // 递归结束,未查询到结果 return []; } } }; ``` 时间复杂度:O(n),假设我们查找到,则递归的次数为 n,所以时间复杂度也为 O(n); leetCood 测试结果(最快结果为 44ms),多次执行测试大都在 60ms 上下,与上一个性能相似: ![测试结果](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170328897-1213610365.png) 当然,测试结果只是一个参考可能不太准确,不过通过多次测试也是可以看出他们之间的差距的。 #### 总结: 以上我们使用了暴力破解、单循环 obj、单循环 map、obj 尾递归、map 尾递归做了对比。 一般对于数组的算法,几乎都可以使用上次思路来解决,当然我们要知道衡量算法指标时间复杂度 O()、空间复杂度 S()。 > 空间复杂度:算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n 为问题的规模,f(n)为语句关于 n 所占存储空间的函数。 > > 通常,我们都是用“时间复杂度”来指运行时间的需求,是用“空间复杂度”指空间需求。 > > 当直接要让我们求“复杂度”时,通常指的是时间复杂度。不过,在一定程度上我们也要考虑算法所需存储空间。 在面试中与实际工作中,简单数组算法的几点经验之谈: 数组去重:使用单循环,结合 obj 或 map 做中间辅助判断; 数组扁平化:使用递归; 树结构的查找与处理:单循环使用 obj/map 做中间辅助判断,同时结合递归思想; 数组的特定重组:除了上述思想外,可能要结合数组常用方法:indexOf(),map(),forEach()或数组高阶函数 filter(),reduce(),sort(),every(),some()等。本文只是抛出一个算法的思路,不再做长篇大论的演示。 ```javascript // 递归思路 // 最简递归:for循环形式 function recursive_simple(array) { for (let i = 0; i < array.length; i++) { const item = array[i]; // 进入递归ifEntry:递归条件,subArray:递归参数 if (ifEntry) { // do something recursive_simple(subArray); } else { // 跳出递归 // do something } } } // 尾递归 function recursive_tail(array, i = array.length - 1, others) { const other = others; /https://img.qb5200.com/download-x/do something // 进入递归,others:其他参数,可以obj、map等一些中间临时变量 if (i > 0) { // do something console.log(i, array[i]); i--; // 递归调用 return recursive_tail(array, i, others); } } ``` #### 涉及方法: indexOf():检测 searchString 在 string、array 是否存在,不过时间复杂度 O(n); map:数组的遍历,返回新的数组,需要手动 return 当前 item;对于数组中对象的 key-value 改写比较适合,时间复杂度 O(n); forEach:改写当前数组,不需要 return,对于直接改写某个数组比较合适; filter:过滤函数,对于过滤数组中符合某个条件的子项比较合适; reduce:接收一个函数作为累加器(accumulator),返回具体数值,对于需要对数组某些子项操作的比较合适,比如求和,斐波那契数列等的处理, reduce(function(total, currentValue, currentIndex, arr), initialValue); sort:适合数组中,复杂比较关系的,一般用于排序用途; every:数组迭代方法,对数组中每一项运行给定函数,如果该函数对每一项返回 true,则返回 true; some:数组迭代方法,对数组中每一项运行给定函数,如果该函数对任一项返回 true,则返回 true,与 every 有区别,如其名:every:每一项,some:任一项; 微信公众号:前端开发那些事儿,欢迎关注! ![前端开发那些事儿](https://img2020.cnblogs.com/blog/937177/202003/937177-20200330170358587-1936298162.gif)

加载全部内容

相关教程
猜你喜欢
用户评论