算法练习3

今日共练习4 道题主题覆盖二分查找与二叉树遍历。1. 二分查找题目在严格升序且无重复的数组中查找target存在则返回下标否则返回-1。核心思想每轮通过中点mid排除一半区间。public int search(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else if (nums[mid] target) { left mid 1; } else { return mid; } } return -1; }重点nums[mid] target目标只可能在左半区间。 nums[mid] target目标只可能在右半区间。 nums[mid] target直接返回 mid。复杂度时间复杂度O(log n) 空间复杂度O(1)二分查找的核心不变量只要 target 存在它一定在当前闭区间 [left, right] 中。2. 搜索插入位置题目在严格升序数组中查找target存在则返回下标不存在则返回应插入的位置。示例nums [1, 3, 5, 6] target 5 - 2 target 2 - 1 target 7 - 4 target 0 - 0核心代码与普通二分几乎相同区别只在于循环结束后的返回值public int searchInsert(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }为什么返回left循环结束时 left right 1。 right 指向最后一个小于 target 的位置 left 指向第一个大于 target 的位置。 将 target 插入 left 位置数组仍能保持升序。复杂度时间复杂度O(log n) 空间复杂度O(1)3. 在排序数组中查找第一个和最后一个位置题目在非递减数组中找到target的起始下标和结束下标不存在则返回[-1, -1]。示例nums [5, 7, 7, 8, 8, 10] target 8 结果[3, 4]普通二分在找到target后不能直接返回因为数组中可能包含重复元素。解决方式进行两次边界二分。第一次找第一个 target。 第二次找最后一个 target。完整实现public int[] searchRange(int[] nums, int target) { return new int[]{findFirst(nums, target), findLast(nums, target)}; } private int findFirst(int[] nums, int target) { int left 0; int right nums.length - 1; int answer -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { if (nums[mid] target) { answer mid; } right mid - 1; } } return answer; } private int findLast(int[] nums, int target) { int left 0; int right nums.length - 1; int answer -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else { if (nums[mid] target) { answer mid; } left mid 1; } } return answer; }关键规律找第一个 target 命中 target 后记录 mid继续向左找。 找最后一个 target 命中 target 后记录 mid继续向右找。复杂度时间复杂度O(log n) 空间复杂度O(1)4. 二叉树的中序遍历题目返回二叉树的中序遍历结果。中序遍历顺序左子树 - 当前节点 - 右子树节点定义static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this.val val; } }递归实现public ListInteger inorderTraversal(TreeNode root) { ListInteger result new ArrayList(); traverse(root, result); return result; } private void traverse(TreeNode node, ListInteger result) { if (node null) { return; } traverse(node.left, result); result.add(node.val); traverse(node.right, result); }递归终止条件if (node null) { return; }三种基础遍历顺序前序遍历根 - 左 - 右 中序遍历左 - 根 - 右 后序遍历左 - 右 - 根复杂度时间复杂度O(n) 空间复杂度O(n)其中空间主要包括结果列表和递归调用栈。