阅读 128

JS算法之0~n-1中缺失的数字及二叉搜索树的第k大节点

0~n-1中缺失的数字

剑指Offer 53 - II. 0~n-1中缺失的数字

难度:简单

题目:leetcode-cn.com/problems/qu…

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

示例1:

输入: [0,1,3] 输出: 2 复制代码

示例2:

输入: [0,1,2,3,4,5,6,7,9] 输出: 8 复制代码

限制:1 <= 数组长度 <= 10000

题解

遇到排序数组中的搜索问题,首先要想到「二分查找」解决!

二分查找

因为范围是从0开始的,所以我们的下标刚好可以当作元素的值。

  • 设left指向0,right指向末尾元素,计算中间值mid

  • 循环条件为left <= right,mid值判断:

    • mid > nums[mid],由题意知,不存在这种情况。

    • mid < nums[mid],说明[left, mid]内缺失元素,要对该区域继续二分查找,因此right要更新为mid - 1。

    • mid = nums[mid],说明[left, mid]内部缺失元素,要对 [mid, right]继续二分查找,因此left要更新为mid + 1。

  • 返回left的下标即为缺失的值。

/**  * @param {number[]} nums  * @return {number}  */ var missingNumber = function (nums) {   let left = 0,     right = nums.length - 1;   while (left <= right) {     let mid = Math.floor((left + right) / 2);     if (mid < nums[mid]) {       right = mid - 1;     } else if (mid === nums[mid]) {       left = mid + 1;     }   }   return left; }; 复制代码

  • 时间复杂度:O(logNlogNlogN)

  • 空间复杂度:O(111)


二叉搜索树的第k大节点

剑指Offer 54.二叉搜索树的第k大节点

难度:简单

题目:leetcode-cn.com/problems/er…

给定一棵二叉搜索树,请找出其中第k大的节点。

示例1:

输入: root = [3,1,4,null,2], k = 1    3   / \  1   4   \    2 输出: 4 复制代码

示例2:

输入: root = [5,3,6,2,4,null,null,1], k = 3        5       / \      3   6     / \    2   4   /  1 输出: 4 复制代码

题解

一看到二叉搜索树,就应该想到中序遍历!

一开始想到的其实是暴力解决,即将所有节点遍历一遍将值存进Set里面后再进行sort,最后返回第k大,但是发现这种方法并未利用到二叉搜索树的特性,故抛弃这种做法。

二叉搜索树的特点是右子树>根>左子树,而中序遍历是左根右的顺序,因此「求二叉搜索树的第k大节点」可以转换为「这棵树中序遍历倒序的第k个节点」。

中序遍历:

function inOrder(root){   if(!root) return null;   inOrder(root.left); // 左   console.log(root.val); // 根   inOrder(root.right); // 右 } 复制代码

中序遍历倒序:

function inOrder(root){   if(!root) return null;   inOrder(root.right); // 右   console.log(root.val); // 根   inOrder(root.left); // 左 } 复制代码

求第k大节点,需要:

  • 在递归遍历时,记录每个节点的序号,例如根节点的右子树为1,根节点为2,...;

  • 当递归到第k个时,记录结果并返回,无需往后递归。

题解如下:

/**  * Definition for a binary tree node.  * function TreeNode(val) {  *     this.val = val;  *     this.left = this.right = null;  * }  */ /**  * @param {TreeNode} root  * @param {number} k  * @return {number}  */ var kthLargest = function (root, k) {   let num = 0,     res = null;   const dfs = function (node) {     if (!node) return;     dfs(node.right);     num++;     if (num === k) {       res = node.val;       return;     }     dfs(node.left);   };   dfs(root)   return res; }; 复制代码

  • 时间复杂度:O(NNN)

  • 空间复杂度:O(NNN)


坚持每日一练!前端小萌新一枚,希望能点个哇~


作者:BrysonLin
链接:https://juejin.cn/post/7028760923053490212


文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐