前言
数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有
写出高质量代码的潜意识。
合并K个升序链表
1.1 问题描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
地址 : 合并K个升序链表
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = [] 输出：[]
示例 3：
输入：lists = [[]] 输出：[]
提示：
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- 10^4 <= lists[i][j] <= 10^4
- lists[i] 按 升序 排列
- lists[i].length 的总和不超过 10^4
1.2 思路讲解
在看这道题之前，可以先去看看我之前写的一篇文章,写的比较详细，可以作为本题的前置知识了。
合并k个链表，其实我们可以简化为，不断的去合并两个链表，采用迭代的方式完成本题。
1.3 AC代码
var mergeTwoLists = function(list1, list2) { const dommy = new ListNode(-1) let p = dommy while(list1 || list2){ if(list1 && list2){ if(list1.val < list2.val){ p.next = list1 list1 = list1.next }else{ p.next =list2 list2 = list2.next } }else if (list1){ p.next = list1 list1 = list1.next }else { p.next = list2 list2 = list2.next } p = p.next } return dommy.next }; var mergeKLists = function(lists) { let result = null for(let i = 0;i < lists.length ; i++){ result = mergeTwoLists(result , lists[i]) } return result };
N - 链表数组长度，K - 链表平均长度
- 时间复杂度O(N^2 * K)
二、删除有序数组的重复项
2.1 问题描述
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
2.2 思路讲解
有序数组，那么迭代每一个元素，判断是否和前一个元素相等，如果相同则使用splice方法去除。
时间复杂度O（N）
var removeDuplicates = function(nums) { for(let i=1;i<nums.length;i++){ if(nums[i]==nums[i-1]){ nums.splice(i,1) i-- } } return nums.length };
提交测试
方法二 : 使用双指针
- 创建一个慢指针 i ，指向数组的第一位，再创建一个快指针 j，指向数组的第二位。
- 若
nums[j]和nums[i]不相等，则先将i+1，然后把nums[i] 改为 nums[j]
var removeDuplicates = function(nums) { let i = 0 for(let j = 1;j < nums.length; j++){ if(nums[i] !=nums[j]){ i++ nums[i] = nums[j] } } return i + 1 };
提交测试
后续
好了，本篇 力扣-寻找两个正序数组的中位数到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。
