长沙网站seo优化,网站建设如何来选择空间,WordPress导购模板,山东网络科技有限公司求解最长递增子序列是一道经典的算法题,
多数解法是使用动态规划的思想#xff0c;算法的时间复杂度是O(); 而Vue.js内部使用的是维基百科提供的一套“贪心二分查找”的算法;
贪心算法的时间复杂度是O(n)#xff0c;二分查找的时间复杂度是O(logn)#xff0c;总时间复杂度…求解最长递增子序列是一道经典的算法题,
多数解法是使用动态规划的思想算法的时间复杂度是O(); 而Vue.js内部使用的是维基百科提供的一套“贪心二分查找”的算法;
贪心算法的时间复杂度是O(n)二分查找的时间复杂度是O(logn)总时间复杂度是O(nlogn)
主要思路
对数组遍历依次求解长度为i时的最长递增子序列
当i元素大于i-1的元素时添加i元素并更新最长子序列
否则往前查找直到找到一个比i小的元素然后插在该元素后面并更新对应的最长递增子序列
主要目的:
让递增序列的差尽可能的小从而可以获得更长的递增子序列是一种贪心算法的思想
源码
!DOCTYPE html
html langenheadmeta charsetUTF-8 /meta http-equivX-UA-Compatible contentIEedge /meta nameviewport contentwidthdevice-width, initial-scale1.0 /titleDocument/title/headbodyscriptfunction getSequence(arr) {const p arr.slice();const result [0]; // 存储长度为I的递增子序列的索引let i, j, u, v, c;const len arr.length;debugger;for (i 0; i len; i) {const arrI arr[i];if (arrI ! 0) {j result[result.length - 1];// result存的最后一个值小于当前值if (arr[j] arrI) {// 存储在result更新前的最后一个索引的值p[i] j;result.push(i);continue;}u 0;v result.length - 1;// 二分搜索查找比arrI小的节点更新result的值while (u v) {c (u v) 1;if (arr[result[c]] arrI) {u c 1;} else {v c;}}if (arrI arr[result[u]]) {if (u 0) {p[i] result[u - 1];}result[u] i;}}}u result.length;v result[u - 1];// 回溯数组p找到最终的索引while (u-- 0) {result[u] v;v p[v];}return result;}const arr [2, 1, 5, 3, 6, 4, 8, 9, 7];const resultIndex getSequence(arr);console.log(最长递增子序列的索引是, resultIndex);let result [];resultIndex.forEach((item, index) {result.push(arr[item]);});console.log(最长递增子序列, result);/script/body
/html
