数据结构与算法
快来分享你的内容吧～
2025-12-23·Java后端使用了归并排序算法, 时间复杂度为O(m+n)查看全文加油鸭：你的题解非常清晰，思路完整，从暴力解法到最优解层层递进，还总结了变式和关键思想！特别是对“从后往前”原地合并的理解很到位，图示+代码+复杂度分析结合得非常好。坚持这种深度思考，算法能力一定会持续提升！411分享- 2025-12-20·Java后端
数组算法题 - 合并两个有序数组
## 合并两个有序数组 [88. 合并两个有序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/merge-sorted-array/) **刷题时间:** - 25/12/23  ### 我的解法 ```java class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { if (n == 0) return; for (int i = m, j = 0; i < m + n; i++) { nums1[i] = nums2[j]; j++; } for (int i = m + n - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (nums1[j] > nums1[j + 1]) { int temp = nums1[j]; nums1[j] = nums1[j + 1]; nums1[j + 1] = temp; } } } } } ``` **优点** - 正确处理了`n==0`的特殊情况 - 先合并再排序的思路 - 使用了经典的冒泡排序法 **缺点** - 时间复杂度高 - 没有利用"有序"的条件 ### 题解 1. **方案一（额外空间合并）:** - 时间复杂度是O($m+n$), 空间复杂度是O($m+n$) - 设置**额外数组存储结果**,采用三指针,最后将结果复制到nums1中 ```java class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] merged = new int[m + n]; int i = 0, j = 0, k = 0; // 双指针合并 while (i < m && j < n) { if (nums1[i] <= nums2[j]) { merged[k++] = nums1[i++]; } else { merged[k++] = nums2[j++]; } } // 处理剩余元素 while (i < m) merged[k++] = nums1[i++]; while (j < n) merged[k++] = nums2[j++]; // 复制回nums1 System.arraycopy(merged, 0, nums1, 0, m + n); } } ``` 2. 方案二(原地合并): - 时间复杂度是O($m+n$), 空间复杂度是O(1) - 与方案一的区别是, **直接在nums1数组上进行操作**, 空间复杂度直接降为O(1) ```java class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { if (n == 0) return; int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) { if (nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; } else { nums1[k--] = nums2[j--]; } } // 运行到这里, 两者必有一个小于0 // 如果是j用完了(nums2),那么程序就可以结束了 // 如果是i先用完了(nums1),那么就把nums2剩余的元素排进去即可 while(j >= 0){ nums1[k--] = nums2[j--]; } } } ``` 1. **思路** - 我的解法使用的是**冒泡排序法**, 先合并数组, 再使用冒泡排序法进行排序 - 时间复杂度是O($(m+n)^2$), 空间复杂度是O(1) - 可以考虑降低为O($m+n$) - **充分利用已知条件**: 两个数组都是"有序"的, 可以使用"**归并排序**"的合并思想 - **使用三个指针** - 一个指针`i`指向nums1的最后有效索引(m-1), 一个指针`j`指向nums2的最后有效索引(n-1),一个指针`k`指向nums1的最后索引(m+n-1) - 比较`nums1[i]`,`nums2[j]`的大小,较大者排到nums1的最末尾(`nums1[k]`). - 直到其中一个数组被比较排序完, 这里有一个边界点: - 就是如果nums2数组先排序完,那么程序可以直接结束了, 因为nums1数组剩余的元素肯定是有序的,且位置正确.  - 如果nums1数组先排序完, 那么可以直接把nums2数组剩余的元素逐个排进nums1即可  2. **算法思想** - **归并排序(有序数据)** - 两个**有序数组**进行**排序**, 那么可以使用**归并排序**的合并思想 - 时间复杂度的优化 - **冒泡排序法**的O($n^2$)时间复杂度, 必然是要被优化的, 需要优化为$O(n)$.  - **双指针/三指针的应用(合并有序数组/链表)** - 指针负责元素的选取, 进行比较 - `nums1[i]` > `nums2[j]` -> 取`nums1[i]`, i-- - 否则 -> 取`nums2[j]`, j-- - 每次k-- - **从后往前操作** - 原地操作 - 这决定了是采用**额外数组存储**,还是**原地操作** - 如果需要"**原地**"修改数组, 且可能会**覆盖未处理数据**时,就不能使用从前往后. - 而是**从后往前** 3. **题目变式 - 思考** - 如果题目要求改为**输出结果为降序**呢? - 两个升序的数组,输出nums1为降序 - 如果采用**原地排序**的办法 - 从前往后: 会直接覆盖未处理的元素(`nums1[0]`), 不管索引从哪里开始 - 从后往前: 也可能会覆盖元素, 例如:  - 如果采用**额外空间**的方法 - 这道题就很简单了 - 同样设置**两个指针**指向两个数组(**从0索引开始**), 比较大小, **较小者放在额外数组的末尾**. 逐个比较存储即可. | 场景 | 最佳解法 | 时间复杂度 | 空间复杂度 | 关键点 | | -------- | -------- | -------- | ------ | ------------ | | 升序（原题） | 从后往前原地合并 | O(m+n) | O(1) | 利用nums1后面的空位 | | 降序 | 额外空间合并 | O(m+n) | O(m+n) | 避免覆盖问题 |
数组算法题 - 两数之和
## 两数之和 **刷题时间:** - 25/12/20  ### 我的解法 ```java class Solution { public int[] twoSum(int[] nums, int target) { int len = nums.length; if (len < 2) return null; int[] result = new int[2]; for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (nums[i] + nums[j] == target) { result[0] = i; result[1] = j; break; //这里仅仅跳出了内存循环, 如果要跳出外层循环,应该设置标记 } } } return result; } } ``` **优点:** - 边界处理正确(len < 2) - 使用了j = i + 1避免重复配对 **缺点:** - O(n^2)的时间复杂度过高, 可能会超时 - 没有充分利用题目信息:"保证存在解", 可以不判断边界 - **bug**: 找到答案后break只跳出了内层循环, 跳出外层循环需要设置标记 **优化:** ```java class Solution { public int[] twoSum(int[] nums, int target) { // 更简洁的边界判断 if(nums == null || nums.length < 2) return new int[0]; //返回空数组而不是null for (int i = 0; i < nums.length - 1; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int[]{i,j}; //直接返回 } } } return new int[0]; //题目保证有解, 不执行 } } ``` ### 题解 ```java class Solution { public int[] twoSum(int[] nums, int target) { // key = 数值, value = 下标 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int gt = target - nums[i]; // 检查补数是否出现过 if (map.containsKey(gt)) { return new int[] { map.get(gt), i }; } // 将当前数值与下标存入哈希表, 这行代码需要放在后面, 防止自己配对自己 map.put(nums[i], i); } return new int[0]; } } ``` 1. **思路:** - 暴力解法的时间复杂度是O(n^2), 空间复杂度是O(1) - 如何优化,**要么减少时间复杂度,要么减少空间复杂度**, 在程序运行中,往往**时间复杂度的优化要优先于空间复杂度** - 那么就优化时间复杂度到O(n). - 两层for循环,**减少到一层for循环即可** - 那么"找两个数的和等于target"可以转变为: "对于`nums[i]`, 查找`target - nums[i]`是否出现过" - 可以采用**哈希表**, 使用哈希表来存储出现过的`nums[i]`,key存储`nums[i]`,value存储`i`(索引) - 在内循环中,判断map中是否存在key = `target - nums[i]`, 如果存在,则输出结果(两个索引) - 如果不存在, 则将`nums[i]`存入map, 等待被匹配 - 哈希表法的时间复杂度是O(n), 空间复杂度是O(n). - 这就是**用空间换时间** 2. **算法思想** - 用**空间换时间 - 哈希表** - **为什么要这样设计**哈希表: `key = 数值, value = 下标` - map.containsKey()可以判断**是否存在键**, 而题目需要判断的就是是否存在`target - nums[i]`. - 题目需要返回的是索引, 那么value就可以**通过key获取索引** - 为什么不能"**先全加入map, 再查找**"? - 可能导致自己匹配自己的情况: (如`[3]`,target=6). - 所以要边查边存 - **边界条件** - 在**我的解法**中, `if (len < 2) return null;` 题目保证有解, 这是可以不判断的 - 但是**这样的编程习惯是好的!**
如何遍历⼀颗⼆叉树
1. 前序遍历（Preorder Traversal） 顺序：根节点 -> 左子树 -> 右子树 递归实现 ```cpp struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void preorderTraversalRecursive(TreeNode* root) { if (root == nullptr) { return; } std::cout << root->val << " "; preorderTraversalRecursive(root->left); preorderTraversalRecursive(root->right); } ``` 迭代实现 ```cpp void preorderTraversalIterative(TreeNode* root) { if (root == nullptr) { return; } std::stack<TreeNode*> stack; stack.push(root); while (!stack.empty()) { TreeNode* node = stack.top(); stack.pop(); std::cout << node->val << " "; if (node->right) { stack.push(node->right); } if (node->left) { stack.push(node->left); } } } ``` 2. 中序遍历（Inorder Traversal） 顺序：左子树 -> 根节点 -> 右子树 递归实现 ```cpp void inorderTraversalRecursive(TreeNode* root) { if (root == nullptr) { return; } inorderTraversalRecursive(root->left); std::cout << root->val << " "; inorderTraversalRecursive(root->right); } ``` 迭代实现 ```cpp void inorderTraversalIterative(TreeNode* root) { if (root == nullptr) { return; } std::stack<TreeNode*> stack; TreeNode* current = root; while (current != nullptr || !stack.empty()) { while (current != nullptr) { stack.push(current); current = current->left; } current = stack.top(); stack.pop(); std::cout << current->val << " "; current = current->right; } } ``` 3. 后序遍历（Postorder Traversal） 顺序：左子树 -> 右子树 -> 根节点 递归实现 ```cpp void postorderTraversalRecursive(TreeNode* root) { if (root == nullptr) { return; } postorderTraversalRecursive(root->left); postorderTraversalRecursive(root->right); std::cout << root->val << " "; } ``` 迭代实现 ```cpp void postorderTraversalIterative(TreeNode* root) { if (root == nullptr) { return; } std::stack<TreeNode*> stack1; std::stack<TreeNode*> stack2; stack1.push(root); while (!stack1.empty()) { TreeNode* node = stack1.top(); stack1.pop(); stack2.push(node); if (node->left) { stack1.push(node->left); } if (node->right) { stack1.push(node->right); } } while (!stack2.empty()) { std::cout << stack2.top()->val << " "; stack2.pop(); } } ``` 总结 前序遍历：根节点 -> 左子树 -> 右子树 中序遍历：左子树 -> 根节点 -> 右子树 后序遍历：左子树 -> 右子树 -> 根节点
一个乱序数组，求第 K 大的数。排序方式使用字典序
要求一个乱序数组中第 K 大的数，并且排序方式使用字典序，可以使用多种方法来实现。这里提供两种常见的方法：一种是直接排序后取第 K 大的数，另一种是使用快速选择算法。 方法一：直接排序 排序：将数组按字典序排序。 取第 K 大的数：从排序后的数组中取出第 K 大的数。 示例代码 ```cpp #include <iostream> #include <vector> #include <algorithm> std::string findKthLargestLexicographical(std::vector<std::string>& arr, int k) { // 按字典序排序 std::sort(arr.begin(), arr.end()); // 取第 K 大的数（注意索引是从 0 开始的） return arr[arr.size() - k]; } int main() { std::vector<std::string> arr = {"banana", "apple", "cherry", "date"}; int k = 2; std::string result = findKthLargestLexicographical(arr, k); std::cout << "第 " << k << " 大的数是: " << result << std::endl; return 0; } ``` 方法二：快速选择算法 快速选择算法是一种高效的查找第 K 大元素的算法，其平均时间复杂度为 O(n)。虽然标准库中的 nth_element 函数也可以实现类似的功能，但这里我们手动实现一个简单的快速选择算法。 示例代码 ```cpp #include <iostream> #include <vector> #include <algorithm> int partition(std::vector<std::string>& arr, int left, int right) { std::string pivot = arr[right]; int i = left - 1; for (int j = left; j < right; ++j) { if (arr[j] <= pivot) { ++i; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[right]); return i + 1; } std::string quickSelect(std::vector<std::string>& arr, int left, int right, int k) { if (left == right) { return arr[left]; } int pivotIndex = partition(arr, left, right); if (k == pivotIndex) { return arr[k]; } else if (k < pivotIndex) { return quickSelect(arr, left, pivotIndex - 1, k); } else { return quickSelect(arr, pivotIndex + 1, right, k); } } std::string findKthLargestLexicographical(std::vector<std::string>& arr, int k) { int n = arr.size(); return quickSelect(arr, 0, n - 1, n - k); } int main() { std::vector<std::string> arr = {"banana", "apple", "cherry", "date"}; int k = 2; std::string result = findKthLargestLexicographical(arr, k); std::cout << "第 " << k << " 大的数是: " << result << std::endl; return 0; } ``` 总结 直接排序：简单易实现，适用于数据量较小的情况。 快速选择算法：效率更高，适用于数据量较大的情况。
【学习笔记】数据结构与算法
#学习笔记# #数据结构与算法# 快期末考试了,有数据结构这一点,大一学java刷算法的时候学了线性表,链表,栈,堆,树等知识,但是图只是知道有这个东西,一直没认真看,加上课程是c语言实现的,有时候原理知道,但是不太会用java代码实现,最近跟着老师的进度以及在mooc看陈越大佬的数据结构视频,大佬不愧是大佬,学到了许多,学习过程中记录了图的部分操作,今晚刚刚看完了图的两种遍历.大家一起学习,一起进步