问题简介
编程思路
- 核心的是要从两个正序数组生成有序的数组。
- 这个是核心。
- 程序使用了在for循环中使用了remove函数
- 使用了List类的不为空就删除。
- 灵活的使用remove函数。
- 这个是核心。
- 中位数的生成
- 数组有奇数个偶数个要进行区分，这样获取中位数。
- 获取中位数要*1.0，成为double，不然会发生截断。
程序编码
第一个AC版本
?这次还挺好的，一下子就AC了。开心。
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] result = getSortedArray(nums1, nums2);
return getMedian(result);
}
private double getMedian(int[] result) {
if (result.length % 2 == 1) {
return result[(result.length - 1)/2] * 1.0;
} else {
return (result[(result.length - 1) / 2] + result[result.length / 2]) * 1.0 / 2;
}
}
private int[] getSortedArray(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length + nums2.length];
List<Integer> list1 = getList(nums1);;
List<Integer> list2 = getList(nums2);;
Integer left = null;
Integer right = null;
for (int i = 0; i < result.length; i++) {
while (!list1.isEmpty() && !list2.isEmpty()) {
if (left == null) {
left = list1.get(0);
}
if (right == null) {
right = list2.get(0);
}
if (left <= right) {
result[i++] = left;
list1.remove(0);
left = null;
} else {
result[i++] = right;
list2.remove(0);
right = null;
}
}
if (list1.isEmpty()) {
while (!list2.isEmpty()) {
result[i++] = list2.remove(0);
}
}
if (list2.isEmpty()) {
while (!list1.isEmpty()) {
result[i++] = list1.remove(0);
}
}
}
return result;
}
private List<Integer> getList(int[] nums) {
return Arrays.stream(nums)
.boxed().collect(Collectors.toList());
}
AC第二个版本
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
return getMedian(getSortedArray(nums1, nums2));
}
private double getMedian(int[] result) {
int length = result.length;
if (isOdd(length)) {
return result[(result.length - 1) / 2] * 1.0;
}
return (result[(result.length - 1) / 2] + result[result.length / 2]) * 1.0 / 2;
}
/**
* 判断一个数字是否为奇数。
* @param num
* @return
*/
private boolean isOdd(int num) {
return num % 2 == 1;
}
private int[] getSortedArray(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length + nums2.length];
List<Integer> list1 = getList(nums1);
List<Integer> list2 = getList(nums2);
Integer left = null;
Integer right = null;
for (int i = 0; i < result.length; i++) {
while (!list1.isEmpty() && !list2.isEmpty()) {
if (left == null) {
left = list1.get(0);
}
if (right == null) {
right = list2.get(0);
}
if (left <= right) {
result[i++] = left;
list1.remove(0);
left = null;
} else {
result[i++] = right;
list2.remove(0);
right = null;
}
}
if (list1.isEmpty()) {
while (!list2.isEmpty()) {
result[i++] = list2.remove(0);
}
}
if (list2.isEmpty()) {
while (!list1.isEmpty()) {
result[i++] = list1.remove(0);
}
}
}
return result;
}
private List<Integer> getList(int[] nums) {
return Arrays.stream(nums)
.boxed().collect(Collectors.toList());
}
总结
?这个题目主要还是使用了int[]数组转换为List集合类，通过灵活使用集合类构造有序数组的方式进行的。
?其中最关键的函数是getSortedArray(int[] nums1, int[] nums2)，尤其是对于left和right的动态更新，当没有值就更新，然后设置之后，把该值置为null，这种小手法用于区分上次循环是哪个变量已经被追加到了result数组。
?一个与之前两个数组比较力扣网-两数相加的不同的地方在于，之前的两个数组索引在变动过程中，i始终指向了两个数组中的相同位置，但是在本程序中，由于两个有序数组在追加过程中无法确认谁先到结尾（数组变为空），因此最后添加了两个if判断list变为空。并不复杂，细细体会可以理解的该问题。
?今天是2021年的除夕，明天就是2022年的春节，一年之计在于春，希望读者在自己的2022年心想事成，刚我爸催我睡觉，现在是2022年1月31日22:45:11，又让父母担心了，我对于我爸太不好了，因为我不喜欢我爸对我妈脾气臭，所以我对我爸的无名之火也不怎么忍受，这么想，其实我应该好好修炼下自己的孝心。
?现在有烟花在后面绽放，我希望2022年父母能够健康如意，家和万事兴。