转摘Java每日一练(20230318) 出现一次的数字、不同的BST、正序数组中位数
目录
[1. 只出现一次的数字](#1. 只出现一次的数字) 🌟
[2. 不同的二叉搜索树](#2. 不同的二叉搜索树) 🌟🌟
[3. 寻找两个正序数组的中位数](#3. 寻找两个正序数组的中位数) 🌟🌟🌟
[🌟 每日一练刷题专栏 🌟](#🌟 每日一练刷题专栏)
[Golang每日一练 专栏](#Golang每日一练 专栏)
[Python每日一练 专栏](#Python每日一练 专栏)
[C/C++每日一练 专栏](#C/C++每日一练 专栏)
[Java每日一练 专栏](#Java每日一练 专栏)
- 只出现一次的数字
============================================================================================
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1示例 2:
输入: [4,1,2,1,2]
输出: 4代码：
java
class Solution {
public int singleNumber(int[] nums){
int res = 0;
for (int num : nums){
res ^= num;
}
return res;
}
};- 不同的二叉搜索树
============================================================================================
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5示例 2：
输入：n = 1
输出：1提示：
1 <= n <= 19
代码：
java
class Solution {
public int numTrees(int n){
if (n < 2){
return 1;
}
int[] count = new int[n + 1];
count[0] = 1;
count[1] = 1;
for (int i = 2; i <= n; i++){
int sum = 0;
for (int root = 1; root <= i; root++){
sum += count[root - 1] * count[i - root];
}
count[i] = sum;
}
return count[n];
}
};二叉搜索树
- 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
- 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
- 它的左、右树又分为二叉排序树
构建二叉排序树
假设有以下数据，按从左到右的顺序来构建二叉排序树。
二叉排序树构建过程：
首先，将8作为根节点
插入3，由于3小于8，作为8的左子树
插入10，由于10大于8，作为8的右子树
插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
插入13，由于13大于8，进入右子树10，又13大于10，进入右子树14,13小于14，则13为14的左子树
只要左子树为空，就把小于父节点的数插入作为左子树
只要右子树为空，就把大于父节点的数插入作为右子树
如果不为空，就一直往下去搜索，直到找到合适的插入位置
任意一树二叉搜索树的水平投影都是有序的，也就是中序遍历的结果是有序的。
- 寻找两个正序数组的中位数
====================================================================================================================================
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
进阶： 你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
代码：
java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int nums1Size = nums1.length;
int nums2Size = nums2.length;
int na = nums1Size + nums2Size;
int[] ns = new int[4 * na];
int i = 0, j = 0, d = 0;
int m = na / 2 + 1;
while (d < m) {
int n = 0;
if (i < nums1Size && j < nums2Size) {
n = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
} else if (i < nums1Size) {
n = nums1[i++];
} else if (j < nums2Size) {
n = nums2[j++];
}
ns[d++] = n;
}
if (na % 2 == 1) {
return ns[d - 1];
}
return (ns[d - 1] + ns[d - 2]) / 2.0;
}
}🌟[每日一练刷题专栏](https://blog.csdn.net/boysoft2002/category_10752746.html " 每日一练刷题专栏") 🌟
**✨**持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
|-----------------------------------------------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
|  | [Golang每日一练 专栏](https://blog.csdn.net/boysoft2002/category_10752343.html "Golang每日一练 专栏") ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
|  | [Python每日一练 专栏](https://blog.csdn.net/boysoft2002/category_12227421.html "Python每日一练 专栏") ----------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
|  | [C/C++每日一练 专栏](https://blog.csdn.net/boysoft2002/category_12227416.html "C/C++每日一练 专栏") -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
|  | [Java每日一练 专栏](https://blog.csdn.net/boysoft2002/category_11518652.html "Java每日一练 专栏") ----------------------------------------------------------------------------------------------------------------------------------------------------------------- |
===========================
【来源： CSDN】
【作者： Hann Yang】
【原文链接】 https://hannyang.blog.csdn.net/article/details/129556015
声明：转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与本网联系，我们将及时更正、删除，谢谢。